[백준 / 골드1] 13460 구슬 탈출 2 (Java)

문제 보기

사용한 것

• 빨간색 구슬이 구멍에 통과하는 이동 횟수를 구하기 위한 BFS
• 빨간색, 파란색 구슬의 좌표, 이동 횟수를 저장하기 위한 Marble
• 이동하면 구슬들의 좌표와 이동 횟수 증가하므로 새로운 Marble 인스턴스를 만들어주기 위한 getNew()

풀이 방법

• N, M을 입력 받고 현재 맵 상태를 입력 받으며 저장한다.
  • 'R', 'B'인 경우 marble의 필드를 수정한다.
  • 'O'인 경우 구멍의 좌표를 holeX, holeY에 저장한다.
• 입력 받은 marble부터 q에 넣어 BFS를 시작한다.
• q가 비어있을 때 까지 하나를 poll하여 curMarble에 저장한다.
  • 만약 curMarble의 ct가 10인 경우 제한 횟수가 지났으므로 건너 뛴다.
• 4가지 방향으로 기울일 수 있으므로 (U, L, D, R) for문을 4번 돌린다.
• 네 방향마다 기울여서 이동시킨 좌표, 이동 횟수를 갱신하기 위해 nextMarble을 getNew()로 생성한다.
• 구슬들이 구멍에 들어갔는지 확인하기 위한 holeR, holeB를 선언한다.
• 현재 방향에 맞게 빨간색 구슬, 파란색 구슬을 벽에 닿지 않을 때까지 이동시킨다.
• 빨간색 구슬이 아직 벽에 닿지 않았으면 빨간색 구슬만 이동시킨다.
• 파란색 구슬이 아직 벽에 닿지 않았으면 파란색 구슬만 이동시킨다.
  • 위 세 과정에서 구슬들이 구멍에 들어가는 경우 holeR, holeB를 true로 변경한다.
• 만약 파란색 구슬이 들어간 경우 이번 이동은 건너 뛴다.
• 만약 빨간색 구슬이 들어간 경우 newMarble의 ct를 반환한다.
• 구슬은 겹쳐있을 수 없기 때문에 이동한 빨간색 구슬과 파란색 구슬의 좌표가 같은 경우 하나의 구슬의 좌표를 변경한다.
  • 위로 기울인 경우 원래 더 아래에 있던 구슬을 한칸 아래로 이동한다.
  • 오른쪽 기울인 경우 원래 더 왼쪽에 있던 구슬을 한칸 왼쪽으로 이동한다.
  • 아래로 기울인 경우 원래 더 위에 있던 구슬을 한칸 위로 이동한다.
  • 왼쪽으로 기울인 경우 원래 더 오른쪽에 있던 구슬을 한칸 오른쪽으로 이동한다.
• q에 newMarble을 넣는다.

코드

public class Main {

    static int N;
    static int M;
    static char[][] map;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int holeX;
    static int holeY;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] split = line.split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);
        map = new char[N][M];
        Marble marble = new Marble();
        marble.ct = 0;
        for (int i = 0; i < N; i++) {
            line = br.readLine();
            for (int j = 0; j < M; j++) {
                char c = line.charAt(j);
                map[i][j] = c;
                if (c == 'R') {
                    marble.redX = i;
                    marble.redY = j;
                } else if (c == 'B') {
                    marble.blueX = i;
                    marble.blueY = j;
                } else if (c == 'O') {
                    holeX = i;
                    holeY = j;
                }
            }
        }

        System.out.println(bfs(marble));
    }

    static int bfs(Marble marble) {
        Queue<Marble> q = new LinkedList<>();
        q.offer(marble);
        while (!q.isEmpty()) {
            Marble curMarble = q.poll();
            if (curMarble.ct == 10) {
                continue;
            }

            for (int i = 0; i < 4; i++) {
                Marble nextMarble = curMarble.getNew();
                boolean holeR = false;
                boolean holeB = false;

                while (map[nextMarble.redX + dx[i]][nextMarble.redY + dy[i]] != '#'
                    && map[nextMarble.blueX + dx[i]][nextMarble.blueY + dy[i]] != '#') {
                    nextMarble.redX += dx[i];
                    nextMarble.redY += dy[i];
                    nextMarble.blueX += dx[i];
                    nextMarble.blueY += dy[i];

                    if (nextMarble.redX == holeX && nextMarble.redY == holeY) {
                        holeR = true;
                    }

                    if (nextMarble.blueX == holeX && nextMarble.blueY == holeY) {
                        holeB = true;
                    }
                }

                while (map[nextMarble.redX + dx[i]][nextMarble.redY + dy[i]] != '#') {
                    nextMarble.redX += dx[i];
                    nextMarble.redY += dy[i];

                    if (nextMarble.redX == holeX && nextMarble.redY == holeY) {
                        holeR = true;
                    }
                }

                while (map[nextMarble.blueX + dx[i]][nextMarble.blueY + dy[i]] != '#') {
                    nextMarble.blueX += dx[i];
                    nextMarble.blueY += dy[i];

                    if (nextMarble.blueX == holeX && nextMarble.blueY == holeY) {
                        holeB = true;
                    }
                }

                if (holeB) {
                    continue;
                }

                if (holeR) {
                    return nextMarble.ct;
                }

                if (nextMarble.redX == nextMarble.blueX && nextMarble.redY == nextMarble.blueY) {
                    if (i == 0) {
                        if (curMarble.redX > curMarble.blueX) {
                            nextMarble.redX -= dx[i];
                        } else {
                            nextMarble.blueX -= dx[i];
                        }
                    } else if (i == 1) {
                        if (curMarble.redY < curMarble.blueY) {
                            nextMarble.redY -= dy[i];
                        } else {
                            nextMarble.blueY -= dy[i];
                        }
                    } else if (i == 2) {
                        if (curMarble.redX < curMarble.blueX) {
                            nextMarble.redX -= dx[i];
                        } else {
                            nextMarble.blueX -= dx[i];
                        }
                    } else {
                        if (curMarble.redY > curMarble.blueY) {
                            nextMarble.redY -= dy[i];
                        } else {
                            nextMarble.blueY -= dy[i];
                        }
                    }
                }

                q.offer(nextMarble);
            }
        }

        return -1;
    }
}

class Marble {

    int redX;
    int redY;
    int blueX;
    int blueY;
    int ct;

    Marble getNew() {
        Marble newMarble = new Marble();
        newMarble.redX = this.redX;
        newMarble.redY = this.redY;
        newMarble.blueX = this.blueX;
        newMarble.blueY = this.blueY;
        newMarble.ct = this.ct + 1;

        return newMarble;
    }
}