BOJ 1103 게임

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

문제

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

---

입력

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

---

출력

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

---

예제 입력 1

3 7
3942178
1234567
9123532

예제 출력 1

5

예제 입력 2

1 10
2H3HH4HHH5

예제 출력 2

4

… 이하 예제 생략

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static boolean isEndless = false;
    static int N, M;
    static int[] dirR = {0, 0, 1, -1}, dirC = {1, -1, 0, 0};
    static int[][] map, dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        dp = new int[N][M];
        // 검사가 완료되지 않았다는 의미로 dp를 MIN_VALUE로 채움
        for (int i = 0; i < N; i++) Arrays.fill(dp[i], Integer.MIN_VALUE);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int input = br.read();
                map[i][j] = input == 'H' ? -1 : input - '0';
            }
            br.readLine();
        }

        int answer = dfs(0, 0);
        System.out.println(isEndless ? -1 : answer + 1);
    }

    static int dfs(int r, int c) {
        // 검사 중인 칸에 접근했다는 것은 동전을 무한히 움직일 수 있다는 의미이므로 isEndless 플래그를 true로 설정
        if(dp[r][c] == -1) {
            isEndless = true;
            return -1;
        }
        // 이미 검사가 완료된 칸은 해당 칸의 최대 이동 가능 수를 반환
        if(dp[r][c] != Integer.MIN_VALUE) return dp[r][c];

        // 검사 중이라는 의미를 표시하기 위해 해당 검사 칸을 -1로 설정
        dp[r][c] = -1;

        /**
         * 해당 검사 칸에서 상하좌우로 움직여 최대로 이동 가능한 수를 max에 저장
         * 움직일 칸이 구멍이거나 보드 밖이면, 해당 검사 단계는 스킵
         * 만약 움직일 칸이 검사 중인 칸이면 무한 루프이므로 즉시 검사 종료
         */
        int max = 0;
        for (int i = 0; i < dirR.length; i++) {
            int newR = r + dirR[i] * map[r][c], newC = c + dirC[i] * map[r][c];
            boolean isInside = newR >= 0 && newR < N && newC >= 0 && newC < M;
            if(isInside && map[newR][newC] != -1)
                max = Integer.max(max, dfs(newR, newC) + 1);
            if(isEndless) return -1;
        }
        // 해당 검사 칸이 검사 완료되었기 때문에 max로 계산된 값을 해당 검사 칸에 저장
        dp[r][c] = max;
        return dp[r][c];
    }
}