[JAVA] BOJ 백준 1103번 - 게임

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1103번: 게임

---

2. 내가 푼 방법

문제를 보자마자 DFS를 떠올렸는데, 실은 DFS에 DP를 사용해 가지치기를 함으로써 시간을 단축시켜야 하는 문제이다.

 

먼저 입력을 받을 때 'H'인 구멍을 0으로 설정해 주었다.

for (int i = 0; i < N; i++) {
    String line = br.readLine();

    for (int j = 0; j < M; j++) {
        char c = line.charAt(j);
        if (c == 'H') arr[i][j] = 0;
        else arr[i][j] = c - '0';
    }
}

 

이제 DP + DFS를 이용해 풀이를 진행하면 된다. 구현에 앞서, visit 배열은 동전이 이동한 경로를 알 수 있으며, true일 경우 이미 동전이 이동했던 위치이므로 무한번 움직일 수 있다는 뜻이다. dp 배열은 해당 위치에 몇 번을 이동했을 때 도착한 것인지를 저장한 것이며, dp 값보다 moveCnt가 더 작을 경우에는 앞선 과정을 그대로 따라가기 때문에 moveCnt가 더 큰 경우만 방문해 준다.

public static void solution() {
    visit[0][0] = true;
    dp[0][0] = 1;

    dfs(0, 0, 1);
}

public static void dfs(int x, int y, int moveCnt) {
    if (result == -1) return;

    dp[x][y] = moveCnt;
    result = Math.max(result, moveCnt);

    for (int d = 0; d < dx.length; d++) {
        int nx = x + dx[d] * arr[x][y];
        int ny = y + dy[d] * arr[x][y];

        if (nx < 0 || ny < 0 || nx >= N || ny >= M || arr[nx][ny] == 0 || dp[nx][ny] > moveCnt) continue;
        if (visit[nx][ny]) {
            result = -1;
            return;
        }

        visit[nx][ny] = true;
        dfs(nx, ny, moveCnt+1);
        visit[nx][ny] = false;
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1103.java

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

class Main {
    static int N, M;
    static int[][] arr;
    static boolean[][] visit;
    static int[][] dp;
    static int result;

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        visit[0][0] = true;
        dp[0][0] = 1;

        dfs(0, 0, 1);
    }

    public static void dfs(int x, int y, int moveCnt) {
        if (result == -1) return;

        dp[x][y] = moveCnt;
        result = Math.max(result, moveCnt);

        for (int d = 0; d < dx.length; d++) {
            int nx = x + dx[d] * arr[x][y];
            int ny = y + dy[d] * arr[x][y];

            if (nx < 0 || ny < 0 || nx >= N || ny >= M || arr[nx][ny] == 0 || dp[nx][ny] > moveCnt) continue;
            if (visit[nx][ny]) {
                result = -1;
                return;
            }

            visit[nx][ny] = true;
            dfs(nx, ny, moveCnt+1);
            visit[nx][ny] = false;
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() 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());
        arr = new int[N][M];
        visit = new boolean[N][M];
        dp = new int[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();

            for (int j = 0; j < M; j++) {
                char c = line.charAt(j);
                if (c == 'H') arr[i][j] = 0;
                else arr[i][j] = c - '0';
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

처음에 DP를 사용하지 않아서 시간초과를 마주했다. 꽤 많은 BFS, DFS 문제들을 풀어왔으면 이제는 좀 시간복잡도부터 확인하자...  다음부턴 반드시!