[백준/Java] 13460 구슬 탈출 2

🔗 문제 링크: https://www.acmicpc.net/problem/13460

 

 

🔍 해결 과정

bfs 시뮬레이션 문제로  빨간 구슬과 파란 구슬이 동시에 움직여 위치를 겹치지 않게 처리하는 과정에서 시간이 걸렸던 문제였습니다.

 

전체적인 과정을 요약하자면 다음과 같습니다.

1️⃣ 빨간 구슬과 파란 구슬의 위치정보, 그리고 이동 횟수를 저장하는 Pair 클래스를 하나 만든다.
2️⃣ 빨간 구슬과 파란 구슬의 위치의 조합이 방문되었는지 확인하기 위해서 4차원 boolean 배열의 형태를 가진 visited 배열을 만든다.
3️⃣ bfs를 통해서 빨간 구슬과 파란 구슬의 이동 정보를 큐에 담을텐데 먼저 보드판을 상하좌우 흔들며 빨간 구슬과 파란 구슬을 이동처리를 한다.
4️⃣ 여기서 빨간 구슬과 파란 구슬이 가는 방향에서 서로 겹치게 된다면 위치에 따라 둘 중 하나를 이전으로 이동시켜야 하므로 boolean 형의 변수 redFirst를 활용한다. 그렇게 해서 빨간 구슬과 파란 구슬의 움직인 최종 위치를 구한다. 
5️⃣ 문제에 조건에 따라서 빨간 구슬이 구멍에 도달했다면 보드판을 움직인 최종 횟수를 반환해준다.
그렇지 않다면 빨간 구슬과 파란 구슬의 현재 위치를 Pair 클래스를 통해서 객체를 만든 다음 큐에 저장해준다. 그리고 빨간 구슬과 파란 구슬 위치 조합을 visited를 통해서 방문 처리 해준다. 
6️⃣ bfs를 통해서 구멍에 도달하지 못했다면 이는 구멍에 도달할 수 없는 상황이므로 -1을 반환한다.

 

코드를 구현하면서 좀 더 구체적으로 디버깅을 하면서 실수한 부분은 없는지 더 정확하게 확인해야 할 필요성을 느끼게 해 준 문제였습니다.

 

---

✏️ 코드

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

class Pair {
    private final int redX;
    private final int redY;
    private final int blueX;
    private final int blueY;
    private final int moveCount;

    public Pair(int redX, int redY,
                int blueX, int blueY, int moveCount) {
        this.redX = redX;
        this.redY = redY;
        this.blueX = blueX;
        this.blueY = blueY;
        this.moveCount = moveCount;
    }

    public int getRedX() {
        return redX;
    }

    public int getRedY() {
        return redY;
    }

    public int getBlueX() {
        return blueX;
    }

    public int getBlueY() {
        return blueY;
    }

    public int getMoveCount() {
        return moveCount;
    }
}

public class Main {

    private static final char TARGET = 'O';
    private static final char BLOCK = '#';
    private static final char RED = 'R';
    private static final char BLUE = 'B';

    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    private static char[][] map;
    private static boolean[][][][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        map = new char[n][m];
        visited = new boolean[n][m][n][m]; // (레드 좌표), (블루 좌표)
        int rStartX = -1;
        int rStartY = -1;
        int bStartX = -1;
        int bStartY = -1;

        for (int i = 0; i < n; ++i) {
            map[i] = br.readLine().toCharArray();

            for (int j = 0; j < m; ++j) {
                if (map[i][j] == RED) {
                    rStartX = i;
                    rStartY = j;
                    continue;
                }

                if (map[i][j] == BLUE) {
                    bStartX = i;
                    bStartY = j;
                }
            }
        }

        // R과 B가 동시에 움직임
        int result = bfs(rStartX, rStartY, bStartX, bStartY);

        bw.write(Integer.toString(result));
        bw.flush();
    }

    private static int bfs(int rStartX, int rStartY,
                           int bStartX, int bStartY) {
        Queue<Pair> q = new ArrayDeque<>();
        visited[rStartX][rStartY][bStartX][bStartY] = true;
        q.offer(new Pair(rStartX, rStartY, bStartX, bStartY, 0));

        while (!q.isEmpty()) {
            Pair cur = q.poll();
            int redX = cur.getRedX();
            int redY = cur.getRedY();
            int blueX = cur.getBlueX();
            int blueY = cur.getBlueY();
            int moveCount = cur.getMoveCount();

            if (moveCount >= 10) { // 10번을 찍었다면 더 이상 못움직임
                continue;
            }

            for (int dir = 0; dir < 4; ++dir) {
                boolean redFirst = false;

                // 먼저 움직일 대상을 찾아야 함.
                if (dir == 0 && redY == blueY && redX < blueX) {
                    redFirst = true;
                } else if (dir == 1 && redY == blueY && redX > blueX) {
                    redFirst = true;
                } else if (dir == 2 && redX == blueX && redY < blueY) {
                    redFirst = true;
                } else if (dir == 3 && redX == blueX && redY > blueY) {
                    redFirst = true;
                }

                int[] redMoveResult;
                int[] blueMoveResult;

                blueMoveResult = move(blueX, blueY, dir);
                redMoveResult = move(redX, redY, dir);

                int redNx = redMoveResult[0];
                int redNy = redMoveResult[1];
                int blueNx = blueMoveResult[0];
                int blueNy = blueMoveResult[1];

                // 만약 좌표 값이 같다면 나중에 움직인 놈을 그 이전으로 되돌리기
                if (redNx == blueNx && redNy == blueNy) {
                    // 만약 타겟 지점이면 유효하지 않으므로 이건 살펴볼 필요가 없음.
                    if (map[redNx][redNy] == TARGET) {
                        continue;
                    }

                    if (redFirst) { // blue 좌표를 이전으로 되돌리기
                        blueMoveResult = moveBack(blueMoveResult, dir);
                        blueNx = blueMoveResult[0];
                        blueNy = blueMoveResult[1];
                    } else {
                        redMoveResult = moveBack(redMoveResult, dir);
                        redNx = redMoveResult[0];
                        redNy = redMoveResult[1];
                    }
                }

                if (map[blueNx][blueNy] == TARGET) {
                    continue;
                }

                // 타겟 지점이면 이것이 정답
                if (map[redNx][redNy] == TARGET) {
                    return moveCount + 1;
                }

                // 이 좌표의 결과를 방문한 적이 있는지 확인하기
                if (visited[redNx][redNy][blueNx][blueNy]) {
                    continue;
                }

                visited[redNx][redNy][blueNx][blueNy] = true;
                q.offer(new Pair(redNx, redNy, blueNx, blueNy, moveCount + 1));
            }
        }

        return -1;
    }

    private static int[] moveBack(int[] pos, int dir) {
        int x = pos[0];
        int y = pos[1];

        if (dir == 0) {
            return new int[]{x + 1, y};
        } else if (dir == 1) {
            return new int[]{x - 1, y};
        } else if (dir == 2) {
            return new int[]{x, y + 1};
        }

        return new int[]{x, y - 1};
    }

    private static int[] move(int x, int y, int dir) {

        int curX = x;
        int curY = y;

        while (true) {
            int nx = curX + dx[dir];
            int ny = curY + dy[dir];

            if (map[nx][ny] == BLOCK) {
                return new int[]{curX, curY};
            }

            if (map[nx][ny] == TARGET) {
                return new int[]{nx, ny};
            }

            curX = nx;
            curY = ny;
        }
    }
}