[백준] 1103. 게임

문제 링크

[백준] 1103. 게임

풀이 과정

DFS 탐색에 DP를 활용하여 문제를 풀어야 합니다.

for (int i = 0; i < N; i++) {
    String s = sc.next();
    for (int j = 0; j < s.length(); j++) {
        char c = s.charAt(j);
        map[i][j] = c - '0' <= 9 ? c - '0' : 0;
    }
}

문제의 입력은 1~9 이므로, 구멍(H)은 0으로 표기했습니다.

System.out.println(dfs(0, 0));

(0, 0) 좌표를 가지고 dfs 메소드 를 호출합니다. 좌표는 DFS 탐색하며, 가장 깊은 곳에서부터의 동전 움직임 횟수를 Top-down 방식으로 누적하고, 그 최종 결과를 출력합니다.

static int dfs(int x, int y) {
    if (!inRange(x, y) || map[x][y] == 0) return 0;
    if (visit[x][y]) {
        System.out.println(-1);
        System.exit(0);
    }
    if (dp[x][y] != -1) return dp[x][y];

    visit[x][y] = true;

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d] * map[x][y], ny = y + dy[d] * map[x][y];
        dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1);
    }

    visit[x][y] = false;

    return dp[x][y];
}

dfs 메소드 는 DFS 탐색과 메모이제이션을 진행합니다. 동작 방식은 다음과 같습니다.

• 좌표 (x, y) 가 맵 밖에 있거나, 구멍이라면 0을 리턴함으로써, 해당 좌표에서는 동전이 움직일 수 없음을 나타냅니다.
• 방문했던 좌표라면, 사이클이 생긴 것이므로 -1을 출력하고 프로그램을 종료합니다.
• 배열 dp의 해당 요소가 변경된 이력이 있다면, 그 값을 바로 리턴함으로써 불필요한 연산 및 재귀 호출을 막습니다.
• 상하좌우 네 방향에 대한 동전의 최대 움직임 횟수를 재귀 메소드를 통해 구해와 최대값을 갱신해줍니다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visit;
    static int[][] dp;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];
        visit = new boolean[N][M];
        dp = new int[N][M];

        for (int[] arr : dp) Arrays.fill(arr, -1);

        for (int i = 0; i < N; i++) {
            String s = sc.next();
            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);
                map[i][j] = c - '0' <= 9 ? c - '0' : 0;
            }
        }

        System.out.println(dfs(0, 0));
    }

    static int dfs(int x, int y) {
        if (!inRange(x, y) || map[x][y] == 0) return 0;
        if (visit[x][y]) {
            System.out.println(-1);
            System.exit(0);
        }
        if (dp[x][y] != -1) return dp[x][y];

        visit[x][y] = true;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d] * map[x][y], ny = y + dy[d] * map[x][y];
            dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1);
        }

        visit[x][y] = false;

        return dp[x][y];
    }

    static boolean inRange(int x, int y) {
        if (x < 0 || x > N - 1 || y < 0 || y > M - 1) return false;
        return true;
    }
}