[JAVA] BOJ 백준 1103번 - 게임

목차

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

---

1. 문제

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

---

2. 내가 푼 방법

간단한 DFS문제이다. 하지만 시간 초과를 고려해야 한다.

 

무한번 움직이는 경우를 찾기 위해 3차원 boolean 배열인 visit을 선언해 주었고,

시간초과를 해결하기 위해 3차원 integer 배열인 cnt를 선언해 주었다.

public static void solution() {
    boolean[][][] visit = new boolean[N][M][4];
    int[][][] dp = new int[N][M][4];

    for (int i = 0; i < 4; i++) {
        dfs(0, 0, i, dp, visit, 1);
    }
}

 

이제 dfs 함수에서 게임이 끝나는 경우를 잘 확인해 주면 된다.

나는 게임이 끝나는 경우, 이미 방문했던 위치일 경우, 얕은 뎁스로 재방문하는 경우를 확인해 주었다.

// i, j 위치에서 direction 방향으로 이동
public static void dfs(int i, int j, int direction, int[][][] dp, boolean[][][] visit, int moveCnt) {
    if (result == -1) return;

    // 게임이 끝나는 경우
    if (i < 0 || j < 0 || i >= N || j >= M || arr[i][j] == 'H') {
        result = Math.max(result, moveCnt-1);
        return;
    }

    // 이미 이동했던 위치라면 리턴
    if (visit[i][j][direction]) {
        result = -1;
        return;
    }

    // 얕은 뎁스로 재방문한다면 리턴
    if (dp[i][j][direction] >= moveCnt) return;

    dp[i][j][direction] = moveCnt;
    visit[i][j][direction] = true;

    // 이동 후 위치
    int[] nextSite = getSite(i, j, direction, arr[i][j]-'0');

    for (int d = 0; d < 4; d++) {
        dfs(nextSite[0], nextSite[1], d, dp, visit, moveCnt+1);
    }

    visit[i][j][direction] = false;
}

---

3. 자바 코드

https://github.com/geujeog/BOJ/blob/main/B1103.java

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

class Main {
    static int N;
    static int M;
    static char[][] arr;
    static int result;

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

    public static void solution() {
        boolean[][][] visit = new boolean[N][M][4];
        int[][][] dp = new int[N][M][4];

        for (int i = 0; i < 4; i++) {
            dfs(0, 0, i, dp, visit, 1);
        }
    }

    // i, j 위치에서 direction 방향으로 이동
    public static void dfs(int i, int j, int direction, int[][][] dp, boolean[][][] visit, int moveCnt) {
        if (result == -1) return;

        // 게임이 끝나는 경우
        if (i < 0 || j < 0 || i >= N || j >= M || arr[i][j] == 'H') {
            result = Math.max(result, moveCnt-1);
            return;
        }

        // 이미 이동했던 위치라면 리턴
        if (visit[i][j][direction]) {
            result = -1;
            return;
        }

        // 얕은 뎁스로 재방문한다면 리턴
        if (dp[i][j][direction] >= moveCnt) return;

        dp[i][j][direction] = moveCnt;
        visit[i][j][direction] = true;

        // 이동 후 위치
        int[] nextSite = getSite(i, j, direction, arr[i][j]-'0');

        for (int d = 0; d < 4; d++) {
            dfs(nextSite[0], nextSite[1], d, dp, visit, moveCnt+1);
        }

        visit[i][j][direction] = false;
    }

    // direction : 0-위, 1-오, 2-아래, 3-왼
    public static int[] getSite(int i, int j, int direction, int move) {
        if (direction == 0) return new int[]{i-move, j};
        else if (direction == 1) return new int[]{i, j+move};
        else if (direction == 2) return new int[]{i+move, j};
        else return new int[]{i, j-move};
    }

    public static void print() 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 char[N][M];

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

            for (int j = 0; j < M; j++) {
                arr[i][j] = line.charAt(j);
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

N과 M의 범위가 1 ~ 50이었어서 시간 초과를 예상 못했는데.. 시간 복잡도를 고려해 한 번에 제대로 풀 수 있도록 해보자.

 

각 위치마다 네 방향을 갈 수 있어서 4 x 4 x 4 x 4...인데 N x M칸 개수만큼 가능하므로, 시간 복잡도는 4^(N *M) 이다.

계산기를 두드리니 1.4124670321394260368352096670161e+1505 값이 나오는데

문제에서 2초를 제한으로 뒀고 위의 시간복잡도는 2억 이상의 값을 가지므로 시간초과가 나는 것이 당연한 것이었다.

결과적으로 visit과 dp 변수들을 통해 지수 시간의 시간복잡도를 상수 시간의 시간복잡도로 줄었던 것 같다.