백준: 구슬 탈출 시리즈 (Java)

백준 13459번: 구슬 탈출 

백준 13460번: 구슬 탈출 2

백준 15644번: 구슬 탈출 3

백준 15653번: 구슬 탈출 4

 

 

 

 

 

 

 

 

---

 

3달 전 즈음에 구슬 탈출 2를 풀었습니다. 당시 구현에 급급하여 간신히 풀었고, 풀고 나서 '어휴 이런 문제는 꼴도 보기 싫다~' 하고 눈 앞에서 치워버린 기억이 납니다.

다시 풀어보니, 구현이 적당히 많고 까다로우며, 시간 커팅할 부분이 많은 흥미로운 문제라 느껴집니다.

 

풀이

'백준 13459번: 구슬 탈출'을 기준으로 설명합니다.

기본 구현

0) 기울일 때마다 움직이는 건 구슬 2개뿐이므로, 각 구슬의 좌표를 따로 저장하여 관리합시다. 그리고 구멍 좌표도 따로 저장해둡니다.

1) 방향과 빨간 구슬, 파란 구슬 위치에 따라 어느 구슬을 먼저 움직일 지 결정합니다.

2) 구슬 2개를 순서대로 움직입니다. 다른 구슬 or 벽을 만나면 그 전에 멈추고, 구멍을 만나면 들어가서 멈춥니다.

3) 최대 10번 움직이면서, 10번 이내에 구멍으로 빨간 구슬만 들어가는 경우가 있는지 찾습니다.

 

이렇게 적으면 별거 없어보이지만, 일단 구현이 까다롭고, 구현 대충하면 시간초과 뜨기 좋습니다.

 

시간 커팅

0) 저는 백트래킹의 느낌으로 DFS를 사용했는데, BFS가 이동 횟수가 작은대로 순회한다는 점을 생각해보면 BFS가 훨씬 빠릅니다. 저는 이미 DFS에 심취했기에 풀이를 바꾸진 않았습니다. 아래 써있는 1), 2)만 해줘도 충분하더라고요.

1) 지난 번에 기울인 방향으로 또 기울일 필요는 없습니다. 해당 처리를 해주면, 최대 방향 계산 횟수가 4^10에서 4*3^9로 감소합니다. 

2) Memoization

보드의 상태는 빨간 구슬, 파란 구슬의 위치로만 결정됩니다. 따라서 (빨간 구슬의 행, 빨간 구슬의 열, 파란 구슬의 행, 파란 구슬의 열)을 저장하는 4차원 int 배열을 만들어, 만약 해당 위치에 n번만에 도착했다면 n번만에 도착했음을 기록합니다. 이후, n번보다 더 많은 횟수를 이동하여 해당 위치에 도착하는 경우는 최소 경우가 아니기에 방문할 필요가 없습니다.

DFS 풀이 기준,

시간 커팅을 하지 않은 경우 - 320ms

1)을 적용할 경우 - 136ms

2)도 적용한 경우 - 88ms

의 결과가 나옵니다. 근데 그냥 1), 2) 적용 안 하고, BFS만 쓰면 구슬 탈출 2, 3, 4 모두 해결되긴 합니다.

 

구슬 탈출 2, 3, 4 풀기

2: 10번 이내로 모든 경우를 시도하면서, 최솟값만 저장하면 됩니다.

3: 2에서 경로만 저장하면 됩니다.

4: 보드의 크기가 100 이하이기에(경계 제외하면 64), 적당히 100번 이내로 도달하는지 확인해줍니다.

DFS 풀이는 1), 2) 를 하지 않으면 시간 초과가 뜰 수 있습니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static char[][] board;
    static int[] dr = { -1, 0, 1, 0 };
    static int[] dc = { 0, -1, 0, 1 };
    static int holeR, holeC;
    static int M, N;
    static int[][][][] visited; // 위치 상태를 저장할 4차원 int 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        board = new char[M][N];
        visited = new int[M][N][M][N];
        int redR = 0, redC = 0, blueR = 0, blueC = 0;
        for (int i = 0; i < M; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                board[i][j] = str.charAt(j);
                if (board[i][j] == 'R') {
                    redR = i;
                    redC = j;
                }
                if (board[i][j] == 'B') {
                    blueR = i;
                    blueC = j;
                }
                if (board[i][j] == 'O') {
                    holeR = i;
                    holeC = j;
                }
            }
        }
        dfs(0, redR, redC, blueR, blueC, 4);
        System.out.println(0);
    }
    
    
    // 10번 이내로 빨간 구슬만 구멍에 넣는 방법이 있는지 찾는 method
    static void dfs(int cnt, int rR, int rC, int bR, int bC, int prevDir) {
        // cnt - 20: visited 초기값 설정하기 귀찮아서 처리
        if (visited[rR][rC][bR][bC] < cnt - 20) return;
        visited[rR][rC][bR][bC] = cnt - 20;
        
        // 빨간 구슬만 구멍에 들어갔다면 1 출력 후 끝내기
        if (rR == holeR && rC == holeC && (rR != bR || rC != bC)) {
            System.out.println(1);
            System.exit(0);
        }
        
        // 10번 움직였거나, 파란 구슬이 구멍에 들어간 경우
        if (cnt == 10 || (bR == holeR && bC == holeC)) {
            return;
        }
        
        for (int dir = 0; dir < 4; dir++) {
            if (prevDir == dir) continue;
            int[] newR = new int[] {1, 1}, newB = new int[] {1, 1};
            // 빨간 구슬이 먼저 움직이는 경우, 파란 구슬이 먼저 움직이는 경우 비교
            if ((dir == 0 && rR < bR) || (dir == 1 && rC < bC) || (dir == 2 && rR > bR) || (dir == 3 && rC > bC)) {
                newR = move(rR, rC, dir, 'R');
                newB = move(bR, bC, dir, 'B');
            } else {
                newB = move(bR, bC, dir, 'B');
                newR = move(rR, rC, dir, 'R');
            }
            
            dfs(cnt+1, newR[0], newR[1], newB[0], newB[1], dir);
            
            // 되돌리기
            if (newR[0] != holeR || newR[1] != holeC) board[newR[0]][newR[1]] = '.';
            if (newB[0] != holeR || newB[1] != holeC) board[newB[0]][newB[1]] = '.';
            board[rR][rC] = 'R';
            board[bR][bC] = 'B';
        }
    }
    
    // r, c에 있는 color 구슬이 dir 방향으로 움직이는 method
    static int[] move(int r, int c, int dir, char color) {
        if (dir == 0) {
            for (int i = r-1; i >= 0; i--) {
                if (!(board[i][c] == '.' || board[i][c] == 'O')) {
                    board[r][c] = '.';
                    board[i+1][c] = color;
                    return new int[] {i+1, c};
                } else if (board[i][c] == 'O') {
                    board[r][c] = '.';
                    return new int[] {i, c};
                } 
            }
            return new int[] {1, c};
        } else if (dir == 1) {
            for (int j = c-1; j >= 0; j--) {
                if (!(board[r][j] == '.' || board[r][j] == 'O')) {
                    board[r][c] = '.';
                    board[r][j+1] = color;
                    return new int[] {r, j+1};
                } else if (board[r][j] == 'O') {
                    board[r][c] = '.';
                    return new int[] {r, j};
                } 
            }
            return new int[] {r, 1};
        } else if (dir == 2) {
            for (int i = r+1; i < M; i++) {
                if (!(board[i][c] == '.' || board[i][c] == 'O')) {
                    board[r][c] = '.';
                    board[i-1][c] = color;
                    return new int[] {i-1, c};
                } else if (board[i][c] == 'O') {
                    board[r][c] = '.';
                    return new int[] {i, c};
                } 
            }
            return new int[] {M-2, c};
        } else {
            for (int j = c+1; j < N; j++) {
                if (!(board[r][j] == '.' || board[r][j] == 'O')) {
                    board[r][c] = '.';
                    board[r][j-1] = color;
                    return new int[] {r, j-1};
                } else if (board[r][j] == 'O') {
                    board[r][c] = '.';
                    return new int[] {r, j};
                } 
            }
            return new int[] {r, N-2};
        }
    }
}