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

링크

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

1103번: 게임

해설

DFS를 이용하는 문제입니다.

그런데 너무 무지성 DFS를 이용하면 타임아웃이 뜹니다.

바로 DFS 와 DP 를 조금 섞어서 풀어야 합니다.

 

왜 DP가 가능하냐 하면 다른 DFS문제들과는 조금 다른 점이 있습니다.

다른 문제들은 A에서 B로 갔을 때 다시 B에서 A로 가버리지 못하게 항상 검사를 했고

B는 항상 A로 가지 않았습니다.

그러나 이문제는 A에서 B로 갔을 때 다시 B에서 A로 돌아갈 수 있다는 보장이 없습니다.

즉 돌아갈 수 있게 되면 무한대 정답 -1 이 되어버립니다.

 

이러한 차이로 인해 각자의 점은 각자의 최대 갈 수 있는 횟수가 정해집니다.

알고리즘을 정리하면 한 점 A의 갈 수 있는 최대 횟수는 (다음점들의 value 들 중 가장 높은 값) + 1 입니다.

 

간단한 예를 들어보자면 백준의 예제 2번 을 사용해 보겠습니다.

1 10

2H3HH4HHH5

위와 같이 테이블이 만들어집니다.

위의 테이블에서 9번째 칸에서 이동할 수 있는 곳은 없습니다.

고로 9번에서 출발할 경우 최대 이동 횟수는 1 입니다.

5번째 칸에서 이동 가능한 곳은 9번째 칸 밖에 없습니다.

아까 9번째 칸에서 이동가능한 최대 횟수는 1로 구해뒀으니 5번째 칸의 최대 횟수는 2가 됩니다.

2번째 칸에서 이동가능한 곳은 5번째 칸 밖에 없습니다.

역시 마찬가지로 최대 횟수는 3이 됩니다.

마찬가지로 0번째 칸에서 이동 가능한 곳은 2번째 칸 밖에 없습니다.

최대 횟수는 4가 됩니다.

이렇게 계산을 완료하면 0번째 칸에서 출발해서 최대 횟수 정답은 4가 됩니다.

 

현재 설명은 down-top 방식으로 되어 있지만 이것을 반대로 top-down 으로 적용시키면

A 에서 갈 수 있는 4방위에 미리 구해둔 값이 있으면 그걸 그대로 쓰고, 없으면 계산을 실시하면 됩니다.

 

그리고 루프를 찾는 방법은 간단합니다.

똑같은 모양의 bool 테이블을 만들어서 현재 간 곳을 계속 기록하다가 만약 지나간 곳에 도달했다면

해당 위치에서 무한루프를 돌 수 있다는 것이므로 -1 을 return 합니다.

 

아래 코드에 모두 구현되어있습니다.

 

코드

#include <iostream>
using namespace std;
 
int N, M, TABLE[50][50], VALUE[50][50];
bool MEMORY[50][50];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
 
int DFS(int _x, int _y) {
	if (TABLE[_y][_x] == 0) {
		return 0;
	}
	if (VALUE[_y][_x] != 0)
		return VALUE[_y][_x];
	if (MEMORY[_y][_x])
		return -1;
	MEMORY[_y][_x] = true;
	int best = 0;
	for (int i = 0; i < 4; ++i) {
		int nx = _x + dx[i] * TABLE[_y][_x];
		int ny = _y + dy[i] * TABLE[_y][_x];
		if (0 <= nx && nx < M && 0 <= ny && ny < N) {
			int value = DFS(nx, ny);
			if (value == -1)
				return -1;
			best = best > value ? best : value;
 
		}
	}
 
	MEMORY[_y][_x] = false;
	VALUE[_y][_x] = best + 1;
	return best + 1;
}
 
int main()
{
	scanf("%d %d", &N, &M);
	getchar();
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			char ch = getchar();
			TABLE[i][j] = ch == 'H' ? 0 : ch - '0';
		}
		getchar();
	}
	
	printf("%d", DFS(0, 0));
 
	return 0;
}