BOJ 1103 - 게임

* BOJ 1103 - 게임 (https://www.acmicpc.net/problem/1103)

[ 분류 - DFS/ Dynamic programming ]

  여러분이 이 문제가 그래프임을 알았다고 가정하고 정리해보자.

  1. 동전은 (0,0) 에서 시작한다.

  2. 동전이 있는 지점에 있는 숫자만큼 상하좌우로 이동할 수 있다.

  3. 구멍 H에 들어가거나 보드 밖으로 나가는 것도 동전을 움직이는 것으로 간주한다.

  따라서 (0,0)부터 시작해서 상하좌우로 움직일 수 있는 곳의 최대치로 이동한다. 이는 memoization으로 구현할 수 있다. 하지만 무한번 움직일 수도 있는데, 바로 사이클이 생기는 경우다. 사이클이 하나라도 생긴다면 그 안에서 계속 움직일 수 있기 때문에 -1을 출력해줘야 한다. 따라서 memoization 하면서 DFS의 cycle detecting 구문을 합쳐줘야 한다.

  cycle detecting은 개인적으로 이 문제에 DFS가 어울린다고 판단했을뿐, 다른 알고리즘을 사용해도 된다. SCC나 BFS의 위상정렬을 사용해도 되고, 진입 및 진출 차수로 계산하여 cycle 여부를 판단해도 된다.

  만약 이 문제를 풀었다면 아래 문제를 풀어보는 것을 추천한다. 처리가 더 필요한 문제다.

     BOJ 금고 (SAFE) - (https://www.acmicpc.net/problem/14932)

-코드

#include <cstdio>
#include <cstring>
int max_v(int a, int b) { return a > b ? a : b; }
char board[50][51];
int dp[50][50], dy[] = { 0,0,1,-1 }, dx[] = { 1,-1,0,0 }, N, M;
bool vi[50][50], finished[50][50];
bool cycle;
int rec(int y, int x) {
	vi[y][x] = 1;
	int& ret = dp[y][x];
	ret = 1;
	int jump = board[y][x] - '0';
	for (int i = 0; i<4; i++) {
		int ty = y + jump * dy[i], tx = x + jump * dx[i];
		if (0 <= ty && ty < N && 0 <= tx && tx < M) {
			if (vi[ty][tx]) {
				if (finished[ty][tx]) ret = max_v(ret, dp[ty][tx] + 1);
				else cycle = 1;
			}
			else ret = max_v(ret, rec(ty, tx) + 1);
		}
	}
	finished[y][x] = 1;
	return ret;
}
int main() {
	memset(dp, -1, sizeof dp);
	int i, j, ans = 0;
	scanf("%d%d\n", &N, &M);
	for (i = 0; i<N; i++) {
		scanf("%s", board[i]);
		for (j = 0; j < M; j++) if (board[i][j] == 'H')
			dp[i][j] = 0, vi[i][j] = 1, finished[i][j] = 1;
	}
	ans = rec(0, 0);
	if (cycle) printf("-1");
	else printf("%d", ans);
	return 0;
}