[백준 1103번 / C++] 게임

쉽게 생각하고 dfs를 적용해서 해보니 메모리 초과가 떴다. 

즉, 50X50 배열에서 값에 따른 재귀를 계속 호출하면서 스택에 함수가 계속 쌓이게 된다.

이로인해서 메모리 초과가 발생하게 되는것이다. 

 

그렇기 때문에 방문 했던 곳에 대한 카운트 값을 기록 즉, 메모이제이션 DP를 활용해야했던 문제였다. 

 

먼저, 다음 그림의 예제값으로 그림을 그려보자.

 

---

 

(0,0) 좌표에 해당하는 값은 "2" 이다. 그렇다면 상하좌우를 살펴보면서 갈 수 있는 길을 찾게 된다.

나아가야 할 방향의 순서를 "우좌상하" 라고 가정하고 한번 풀어보겠다.

그렇다면 먼저 오른쪽 방향으로 먼저 가보겠다. 이때 vsited(좌표값) 에 방문했다고 체크를 해두자. 

 

오른쪽 방향에서 만나는 숫자는 3이다. 여기서도 똑같이 vsited(좌표값) 에 방문했다고 체크를 한다. 

오른쪽 방향에서 만나는 숫자는 1이다. 여기서도 똑같이 vsited(좌표값) 에 방문했다고 체크를 한다. 

오른쪽으로 갈 수 없으니 리턴해주고 왼쪽으로 간다. 리턴해주는 그림은 여기서 생략하였다.  

왼쪽 방향에서 만나는 숫자는 10이다. 여기서도 똑같이 vsited(좌표값) 에 방문했다고 체크를 한다. 

 

이후 10의 값으로 이동하려면 map 범위를 초과한다. 지금부터가 중요하다.

재귀를 호출하여 값을 갱신해 나갔는데 리턴을 하면서 지금까지 갈 수 있었던 거리값을 +1 씩 리턴을 해준다는 것이다. 그림과 같이 dp라는 배열에서 방문했던 순서 역순으로 하나하나씩 갱신해준다. 

 

만약 해당 Map 에서 사이클이 돌지 않는다면 (0,0)의 좌표값의 dp 값은 4가 된다.

이런식으로 dp값이 정해져있다면 바로 리턴해주고 리턴을 받은 재귀함수에서는 현재 자신이 들고 있는 dp값과 리턴받은 dp+1 값을 비교해서 큰 값을 dp에 저장하면 된다. 

 

하지만 위의 예제에서

 

우  우  우  하  좌 

2->3->10->3->3  다음  "좌 우 좌 우 ...... " 반복 되기 때문에 출력값은 -1 이 돼야한다는 점을 생각해야한다. 

 

즉, 이미 방문했던 곳을 또 가게 되는 경우에는 -1 을 출력해야한다. 

 

추가적으로 재귀를 돌 때 상하좌우를 다 살펴보고 나면 visted를 다시 0으로 초기화하지 않는다면 다른 재귀에서 돌아보지 않았던 map을 값이 생성 되어있어서 잘못된 리턴값을 받지 않도록 주의하자.  

 

#include <iostream>
#include <algorithm>
using namespace std;
int m, n;
int map[50][50];
int visited[50][50];
int dp[50][50]; 
int min_n = -1;
int dfs(int y, int x) {	
	if (x < 0 || x >= n || y < 0 || y >= m||map[y][x]==-1)return 0; 
	if (visited[y][x] == 1) {
		cout << -1;
		exit(0);
	}
	if (dp[y][x])return dp[y][x]; 
	visited[y][x] = 1; 
	int dis = map[y][x]; 
	int dx[4] = { 0,0,dis,-dis };
	int dy[4] = { dis,-dis,0,0 };
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i]; 
		int ny = y + dy[i]; 
		dp[y][x] = max(dp[y][x],dfs(ny, nx)+1); 	
	}
	visited[y][x] = 0; 
	return dp[y][x]; 
}
int main() {
	cin >> m >> n;
	for (int y = 0; y < m; y++) {
		string s; cin >> s;
		for (int x = 0; x < n; x++) {
			if (s[x] == 'H')map[y][x] = -1;
			else map[y][x] = s[x] - '0';
		}
	}	
	cout << dfs(0, 0); ;
}

1103번: 게임