백준 1103번 - 게임(C++, dfs를 DP로 최적화)

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

 

문제를 처음 봤을 때 가장 먼저 떠올라야하는 것은 dfs이다. 어딘가 최소거리로 도착하는 것도 아니고 한 노드에 도착한 후에 4방향으로 가장 멀리 가는 것이 목표이기 때문에 bfs를 적용하는 것은 옳지 않다.

하지만 dfs로 모든 방법을 찾는 것은 시간이 매우 오래걸린다. N^M 의 크기를 갖고 있고, 만약 모든 노드의 크기가 1이라면 

한 노드에서 나아갈 수 있는 방향은 4방향이므로

 

O(4^N *M) 의 매우 큰 시간이 소모된다. 그래서 dfs를 dp로 최적화해야한다. 예제를 살펴보자 

 

3	9	4	2	1	7	8
1	2	3	4	5	6	7
9	1	2	3	5	3	2

 

0,0 에서 왼위아래 모두 갈 수 없다. 그렇다면 오른쪽으로 가야하고 왼쪽으로 세칸이니까 0, 3으로 이동하게 되면 2가 있다. 2는 세방향 이동할 수 있다.

왼쪽으로 이동할 경우 0,1 로 가게되고 0,1 의 9는 아무곳도 갈 수 없다. 끝

오른쪽으로 이동할 경우 0, 5로 가게 되고 0,5의 7은 아무곳도 갈 수 없다. 끝

아래로 이동할 경우 2,3 으로 가게 되고 3은 왼쪽, 오른쪽으로 갈 수 있다. 

2,3 에서 2, 0 or 2, 6으로 이동가능하다.

 

여기까지만 살펴보고 상황을 보자. 0,0에서 시작해서 0,3으로 이동하고 나서 세가지 경우가 발생했다. 0,3 은 세가지 경우 중 아래로 이동할 경우 가장 많은 이동거리를 확보할 수 있었다. 그리고 이 결과는 0,3으로 어느 방향에서 도착했던 간에 이 결과는 바뀌지 않는다. 그래서 이 결과들을 메모이제이션 해두고 다시 사용할 수 있는 것이다.

 

즉 dp[0][3] 의 경우 처음에는 0이었다가

dp[0][3] = 1 -> 왼, 오 이동

dp[0][3] = 3 -> 아래 이동

 

이렇게 갱신이 되고 이후 어떠한 경로에서 0,3 에 도착하였을 때는 그대로 값을 사용하면 된다.

 

그래서 점화식을 새워보면

 

dp[x][y] = max(dp[x][y], f(nextx, nexty) + 1)

 

일단 다음 dfs 이동이 된다는 건 1번은 이동된다는 뜻이기 때문이다. 그리고 만약 dp가 채워져있다면 dfs하지 않고 그 값을 그대로 사용해준다.

 

이러면 O(N * M)으로 시간을 매우 절약할 수 있다. 구현이 조금 어려웠다.

 

#include <iostream>

using namespace std;

int dp[51][51] = {0,};
char board[51][51];

bool visited[51][51] = {false,};
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int N, M;

bool range(int x, int y){
	return x > -1 && x < N && y > -1 && y < M;
}

int dfs(int x, int y){
	if(visited[x][y]) {
		cout << -1 << '\n';
		exit(0);
	}

	if(dp[x][y] != 0) return dp[x][y];

	visited[x][y] = true;

	int num = board[x][y] - '0';

	for(int i = 0; i < 4; i++){
		int nx = x + dx[i] * num;
		int ny = y + dy[i] * num;

		if(range(nx, ny) && board[nx][ny] != 'H'){ // 4방향 돌며 갈 수 있는 곳들 계속 갱신
			dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);
		}
	}

	visited[x][y] = false; // 다 돌았으면 방문 체크 해제, 다른 경로를 통해 들어올수도 있기 때문
	return dp[x][y]; // 갱신한 dp값을 출력. 더이상 갈 수 없는 부분이라면 0을 내보낼 것임
}

int main(){
	cin >> N >> M;

	for(int i = 0; i < N; i++){
		string tmp; cin >> tmp;
		for(int j = 0; j < M; j++){
			board[i][j] = tmp[j];
		}
	}

	cout << dfs(0, 0) + 1 << '\n';
}