[백준 / JAVA] 1103번 게임

문제

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

접근

길찾기 문제와 비슷한 결이다. DFS와 BFS 둘 다 가능할 것 같은데, 최단 경로를 구하는 것이 아니기 때문에 DFS를 선택.
시간 초과 걱정을 하긴 했지만, 일단 해보기로...

문제는 동전을 무한 번 움직일 수 있는 경우이다.
카운트가 일정 값 이상일 때 무한 번이라고 판단할까? 당연히 불가능하기 때문에 방문했던 위치를 체크할 필요가 있다.
이동했을 때 도착한 위치가 이전에 방문했던 위치라면 다시 똑같은 방법으로 돌아올 수 있기 때문에 무한 번 방문할 수 있다.

일반적인 길찾기 문제에서처럼 상하좌우를 한 칸씩 이동하는 것이 아니라 해당 위치의 값만큼 이동한다. 따라서, 방향만 정해주고 값을 곱해서 이동시켜 준다.

상하좌우로 이동하면서 cnt를 증가시키고

1. 도착한 위치가 보드 범위를 벗어나거나 'H'라면, cnt와 max를 비교한다.
2. 도착한 위치가 이전에 방문했던 위치라면, -1을 출력한다.

---

위 풀이에서는 시간 초과가 발생했고 해결하지 못하여 풀이를 참고했다.

결국 DP였다.
위 풀이의 문제점은 다른 트리에서 방문한 위치를 다시 방문하여 DFS를 또 실행한다는 점이다.

위 그림에서 [p][q]와 [r][p]가 같은 위치일 수 있다.
이런 경우에는 dfs 메소드를 중복하여 실행하기 때문에 이런 경우에 memoization을 사용하여 시간을 단축시킬 수 있다.

dfs 메소드를 실행하기 전, dp 배열의 값과 cnt 값을 비교하여 가지치기를 할 수 있다.

풀이

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

public class boj_1103 {
    //public class Main {
    static int max = 0;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        char[][] map = new char[n][m];
        boolean[][] visited = new boolean[n][m];
        int[][] dp = new int[n][m];

        for (int i = 0; i < n; i++) {
            String str = br.readLine();

            for (int j = 0; j < m; j++) {
                map[i][j] = str.charAt(j);
            }
        }

        visited[0][0] = true;
        dfs(0, 0, n, m, map, visited, dp, 0);

        if (max == Integer.MAX_VALUE) System.out.println("-1");
        else System.out.println(max);
    }

    static void dfs(int row, int col, int n, int m, char[][] map, boolean[][] visited, int[][] dp, int cnt) {
        cnt++;
        dp[row][col] = cnt;

        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i] * (map[row][col] - '0');
            int nc = col + dc[i] * (map[row][col] - '0');

            if (!isRange(nr, nc, n, m) || map[nr][nc] == 'H') {
                if (cnt > max) max = cnt;
                continue;
            }

            if (visited[nr][nc]) {
                max = Integer.MAX_VALUE;
                break;
            }

            if (dp[nr][nc] > cnt) continue;

            visited[nr][nc] = true;
            dfs(nr, nc, n, m, map, visited, dp, cnt);
            visited[nr][nc] = false;
        }
    }

    static boolean isRange(int r, int c, int n, int m) {
        return r >= 0 && c >= 0 && r < n && c < m;
    }
}

정리

접근 자체에 문제는 없었으나, 시간을 단축시킬 수 있는 방법을 찾지 못했다.

DFS에서 시간을 단축시킬 수 있는 두 가지 방법을 잘 기억하자.

1. Memoization: 재귀적으로 동일한 상태를 여러 번 탐색하는 경우, 이미 계산된 결과를 저장하고 재사용함
2. 가지치기: 특정 조건을 만족하지 않는 경로를 조기에 차단하여 불필요한 탐색을 줄임