[백준] 1103: 게임 (JAVA)

🔗 문제 링크

1103번: 게임

---

⏳ 풀이

DFS + DP

1. 원점 (0,0)을 기준으로 DFS를 통해 움직일 수 있는 모든 경로를 고려하며 동전을 움직인다.

2. DP 배열을 활용해 경로마다 동전이 움직인 횟수를 저장한다.

3. DFS를 돌면서 방문처리 배열과 DP 배열을 활용해 아래와 같은 경우 가지치기를 해준다.

   • 동전이 범위를 벗어나거나 구멍에 빠진 경우
   • 다른 경로에서 이미 방문한 지점인데 현재 경로보다 더 많은 횟수로 방문한 경우 (핵심!)
   • 한 경로에서 같은 지점에 다시 방문한 경우 (무한루프 처리 후 return)

---

💡 고찰

• DP 배열을 사용하지 않으면 시간초과가 발생하는 문제다. 최악의 경우 4^(NM)의 경우의 수를 생각해야 한다. DP 배열을 활용해야 한다! 라는 것만 알면 구현하는데는 큰 어려움은 없는 문제였다.

• 구멍에 빠지는 경우 혹은 범위를 벗어나는 경우는 움직임이 아니라고 생각했지만 구멍에 빠지거나 범위를 벗어나는 순간까지의 움직임을 포함해야 했다. 예제 5번 테스트케이스를 미리 확인했으면 고려했을 상황이였다.. 문제에서 예제로 제시해준 모든 테스트케이스를 확인하는 것도 중요한 것 같다.

💻 소스코드

mport java.io.*;
import java.util.*;

public class Main_bj_1103_게임 {

    static int N, M, map[][], dp[][], max;
    static boolean v[][], loop;
    static int di[] = {0, 0, -1, 1};
    static int dj[] = {1, -1, 0, 0};

    public static void main(String[] args) throws Exception {

        System.setIn(new FileInputStream("res/input.txt"));
        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];
        v = new boolean[N][M];
        max = Integer.MIN_VALUE;
        loop = false;

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        v[0][0] = true;
        dfs(0, 0, 1);

        if (loop) max = -1;
        System.out.println(max);

    }

    static void dfs(int x, int y, int cnt) {

        max = Math.max(max, cnt);

        for (int d = 0; d < 4; d++) {

            int dx = x + di[d] * map[x][y];
            int dy = y + dj[d] * map[x][y];

            if (dx < 0 || dx >= N || dy < 0 || dy >= M || map[dx][dy] == 24) continue;

            if (v[dx][dy]) {
                loop = true;
                return;
            }

            if (dp[dx][dy] >= cnt + 1) continue;

            v[dx][dy] = true;
            dp[dx][dy] = cnt + 1;
            dfs(dx, dy, cnt + 1);
            v[dx][dy] = false;
        }
    }
}