1. 문제 분석하기

1.1. 문제 의도

• 시뮬레이션 문제입니다.

1.2. 문제 조건

1. 동전은 가장 왼족 위 (0, 0)에 있다.
2. 동전이 있는 칸의 숫자만큼 상, 하, 좌, 우 중 한 방향으로 이동한다.
   (이때, 중간에 지나치는 구멍은 무시한다.)
3. 구멍에 빠지거나 보드 바깥으로 나간다면 게임은 종료한다.
4. 무한번 움직일 수 있다면 -1을 출력한다.

2. 문제 해결하기

• 이 문제의 핵심 아이디어는 상, 하, 좌, 우를 이동했을 때 가장 오래 게임을 할 수 있는 경우를 선택하는 것입니다.
  • 즉, 현재 동전이 있는 칸을 (cy, cx)라고 할 때,
    다음 동전이 이동할 칸을 (ny, nx)라고 한다면,
  • (cy, cx)의 최대 게임 횟수는 4방향에 대한 게임 횟수들 중 최대값을 저장합니다.
  • 이때 (ny, nx)가 구멍에 빠지거나, 범위를 초과한다면 바로 프로그램 종료합니다.
• 따라서 이 문제는 DP가 결합된 시뮬레이션 문제입니다.
• 동전이 무한번 움직이는 경우는 cycle이 생성되는 경우입니다. 방문표시를 한 곳에 다시 왔다면 cycle이 발생한 것이니 프로그램을 종료합니다.

3. 코드

#include <iostream>
#include <cstdlib>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MAX 50
using namespace std;

int N, M, dp[MAX][MAX];
char map[MAX][MAX];
bool visited[MAX][MAX];
int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

bool checkRange(int cy, int cx) {
	return (0 <= cy && cy < N) && (0 <= cx && cx < M);
} 

int solve(int cy, int cx) {
	if (visited[cy][cx]) { cout << -1; exit(0); }
	if (dp[cy][cx]) return dp[cy][cx];
	
	int weight = map[cy][cx] - '0';
	visited[cy][cx] = true;
	for (int i = 0; i < 4; ++i) {
		int ny = cy + weight * d[i][0], nx = cx + weight * d[i][1];
		if (!checkRange(ny, nx) || map[ny][nx] == 'H') continue;
		dp[cy][cx] = max(dp[cy][cx], solve(ny, nx) + 1);
	}
	visited[cy][cx] = false;
	return dp[cy][cx];
}
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < N; ++i) cin >> map[i];
    cout << solve(0, 0) + 1;
}

4. 결과