[ Baekjoon ] 1103. 게임

www.acmicpc.net/problem/1103

1103번: 게임

풀이 방법

임의의 칸에서 움직일 수 있는 모든 칸에 대해서 DFS 방식으로 확인해보면 된다. 이때, 시간 초과가 발생할 수 있으므로 DP를 이용한다. memo[i][j]에 board[i][j]에서 시작할 때 최대 움직일 수 있는 횟수를 저장하면, 똑같은 위치를 재방문할 때 곧바로 결과값을 알아낼 수 있다.

 

우선 dfs() 함수에서는 현재 위치 cur에서 시작할 때, 최대 움직일 수 있는 횟수를 반환한다고 하자. 만약 현재 위치가 보드의 바깥이거나 구멍이라면 더이상 움직일 수 없으므로 0을 반환한다.

if (!valid(cur)) return 0;
if (board[cur.r][cur.c] == 'H') return 0;

 

그리고 아직 방문한 적이 없다면 다음 위치 next를 계산한다. 만약 next가 이미 방문한 적 있는 위치라면 cycle이 생겼다는 의미이다. 따라서 이 경우에는 -1을 출력하고 프로그램을 종료한다. 그렇지 않다면 memo 원소를 업데이트한다.

const static int dr[4] = { -1, 1, 0, 0 };
const static int dc[4] = { 0, 0, -1, 1 };

if (memo[cur.r][cur.c] <= 0) {
	visit[cur.r][cur.c] = true;
	for (int i = 0; i < 4; i++) {
		int next_r = cur.r + (board[cur.r][cur.c] - '0') * dr[i];
		int next_c = cur.c + (board[cur.r][cur.c] - '0') * dc[i];
		Pos next = Pos(next_r, next_c);
		if (valid(next) && visit[next_r][next_c]) {
			printf("-1");
			exit(0);
		}
		memo[cur.r][cur.c] = max(memo[cur.r][cur.c], dfs(next) + 1);
	}
	visit[cur.r][cur.c] = false;
}

 

전체 코드는 여기서 확인할 수 있다.