[BOJ/백준 1890/C++] 점프

https://www.acmicpc.net/problem/1890

1890번: 점프

 

[문제 요약]

- N x N 게임판에 수가 적혀있다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸까지 규칙에 맞게 이동한다.

- 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 아래쪽이나 오른쪽으로만 이동해야 된다.

- 0은 더 이상 진행을 막는 종착점임으로 마지막칸(가장 오른쪽 아래)에만 존재한다.

- 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하여라

 

예시)

위 그림과 같이 규칙에 따라 이동하면 가장 오른쪽 아래 칸까지 가는 경로의 개수는 3개다.

 

[문제 조건]

- N ( 1 ≤ N ≤ 1000)

- 경로의 갯수는 2^63-1 보다 작거나 같다

- 각 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 같에는 항상 0이 주어진다.

- 시간 제한 1초 , 메모리 제한 128MB 

 

[문제 풀이]

(mp는 원래 테이블(그림 1과 같은 테이블) dp는 경로의 개수를 저장하는 2차원 테이블)

 

문제를 이해하고 나면 아마 대부분의 사람들은 "BFS나 DFS 방법을 이용하면 풀 수 있겠구나" 라는 생각을 할 것이다. 물론 필자도 같은 생각을 했다. 그래서 BFS 방식을 이용하여 맨 처음 위치부터 갈 수 있는 칸을 큐에 집어넣으면서 개수를 저장하는 dp 테이블의 값을 하나씩 증가 시켜나가며 마지막 위치 dp[n-1][n-1]에 도달했을 때 더 이상 진행을 안하는 방법으로 코드를 작성했다.

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <queue>

using namespace std;

int n;
int dx[2] = { 1,0 };
int dy[2] = { 0,1 };
vector<vector<int>> mp;
vector<vector<int>> dp;
queue<pair<int, int>> q;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	mp.resize(n);
	dp.resize(n);
	for (int i = 0; i < n; i++)
	{
		mp[i].resize(n);
		dp[i].resize(n);
	}

	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> mp[i][j];
		
	q.push({ 0,0 });
	while (!q.empty())
	{
		pair<int, int> tmp = q.front(); q.pop();
	
		int multiple = mp[tmp.first][tmp.second];

		for (int i = 0; i < 2; i++)
		{
			int nx = tmp.second + dx[i] * multiple;
			int ny = tmp.first + dy[i] * multiple;

			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

			dp[ny][nx]++;
			if(mp[ny][nx] != 0 ) q.push({ ny,nx });
		}
	}

	cout << dp[n - 1][n - 1];
}

아주 좋다 오늘의 공부는 일찍 끝나겠구나 하고 제출을 누른 순간

 

?????????????????

 

그렇다 쉽게 보내줄 그런 문제가 아니였다.

 

BFS 방식을 이용했을 때 메모리초과가 뜬다면 아마도 DFS도 메모리초과가 떳을 것 같다.

그래서 풀이 방법을 아예 다르게 접근을 해봤다.

 

DP테이블 값의 정의는 그대로 두고(현재 위치까지 올 수 있는 경로의 개수) 모든 위치를 확인하는 대신 dp값이 0이 아닌 위치만 확인 하면서 진행하면서 이동했을 때 도착한 위치의 dp 값은 출발지의 dp값과 도착지의 dp값을 더한 값으로 갱신을 해주었다. 왜냐하면 출발지까지 도달할 수 있는 경로의 개수 + 도착지까지 도달할 수 있는 경로의 개수가 되어야 도착지의 경로의 개수가 논리적으로 말이 된다.

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <queue>

using namespace std;

int n;
int dx[2] = { 1,0 };
int dy[2] = { 0,1 };
vector<vector<int>> mp;
vector<vector<int>> dp;
queue<pair<int, int>> q;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	mp.resize(n);
	dp.resize(n);
	for (int i = 0; i < n; i++)
	{
		mp[i].resize(n);
		dp[i].resize(n);
	}

	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> mp[i][j];
	dp[0][0] = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i == n - 1 && j == n - 1)
			{
				cout << dp[n - 1][n - 1];
				return 0;
			}
			if (dp[i][j] == 0) continue;
			int multiple = mp[i][j];

			for (int a = 0; a < 2; a++)
			{
				int nx = j + dx[a] * multiple;
				int ny = i + dy[a] * multiple;

				if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

				dp[ny][nx] = dp[ny][nx] + dp[i][j];
			}
		}
	}
}

음? 아? 왜? 뭔가 문젠데?

 

이 방법도 틀렸다는건 필자가 문제를 잘 못 이해했을 가능성이 매우 높다.

그래서 다시 문제를 처음부터 꼼꼼히 읽어봤는데, 문제 조건에 이런게 있다.

경로의 갯수는 2^63-1 보다 작거나 같다

음.... int의 범위가 2^32 정도니까 틀릴 수 밖에 없었구나!

 

그래서 dp테이블의 자료형을 long long으로 바꿔주니까 바로 풀렸다.

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <queue>

using namespace std;

int n;
int dx[2] = { 1,0 };
int dy[2] = { 0,1 };
vector<vector<int>> mp;
vector<vector<long long>> dp;
queue<pair<int, int>> q;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	mp.resize(n);
	dp.resize(n);
	for (int i = 0; i < n; i++)
	{
		mp[i].resize(n);
		dp[i].resize(n);
	}

	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> mp[i][j];
	dp[0][0] = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i == n - 1 && j == n - 1)
			{
				cout << dp[n - 1][n - 1];
				return 0;
			}
			if (dp[i][j] == 0) continue;
			int multiple = mp[i][j];

			for (int a = 0; a < 2; a++)
			{
				int nx = j + dx[a] * multiple;
				int ny = i + dy[a] * multiple;

				if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

				dp[ny][nx] = dp[ny][nx] + dp[i][j];
			}
		}
	}
}

굳

 

 

아 근데 BFS나 DFS도 최적화 하면 풀릴 것 같은데.... 나중에 한번 시도해봐야겠다.