[백준 Baekjoon] 13459번 구슬 탈출 - JAVA

[백준 Baekjoon] 13459번 구슬 탈출 - JAVA

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static char[][] board;

    public static int[] dx = {-1, 1, 0, 0}; // 상 하 좌 우
    public static int[] dy = {0, 0, - 1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        board = new char[N][M];
        Marble red = null, blue = null;

        for (int i = 0; i < N; i++) {
            String t = br.readLine();
            for (int j = 0; j < M; j++) {
                char c = t.charAt(j);

                if (c == 'B') {
                    blue = new Marble(i, j);
                } else if (c == 'R') {
                    red = new Marble(i, j);
                }

                board[i][j] = c;
            }
        }

        Queue<Marble[]> queue = new LinkedList<>();
        queue.add(new Marble[]{red, blue});

        // 메모이제이션
        boolean[][][][] visit = new boolean[N][M][N][M];
        visit[red.x][red.y][blue.x][blue.y] = true;

        int cnt = 0;

        while (!queue.isEmpty() && cnt++ < 10) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                Marble[] cur = queue.poll();

                // 위쪽, 아래쪽, 왼쪽, 오른쪽 기울이기
                for (int k = 0; k < 4; k++) {
                    Marble r = new Marble(cur[0].x, cur[0].y);
                    Marble b = new Marble(cur[1].x, cur[1].y);

                    // 겹치는 경우 뒤의 어느 구슬을 움직여야 할지
                    boolean redFirst = isRedFirst(r, b, k);

                    move(r, k); // 겹치는거 상관없이 이동
                    move(b, k);

                    // 파란 구슬이 구멍에 들어간 경우
                    if (board[b.x][b.y] == 'O') continue;

                    // 두 구슬이 같이 지점에서 겹치는 경우
                    if (r.x == b.x && r.y == b.y) {
                        setOrder(r, b, k, redFirst);
                    }

                    // 빨간 구슬만 구멍에 들어간 경우
                    if (board[r.x][r.y] == 'O') {
                        System.out.println(1);
                        return;
                    }

                    // 메모이제이션
                    if (visit[r.x][r.y][b.x][b.y]) continue;
                    visit[r.x][r.y][b.x][b.y] = true;

                    // 기울인 구슬들을 큐에 추가
                    queue.add(new Marble[]{r, b});
                }
            }
        }

        System.out.println(0);
    }

    // 기울이는 방향에 맞춰 구슬의 위치를 비교해서 어느 구슬이 뒤인지
    public static boolean isRedFirst(Marble r, Marble b, int d) {
        if ((d == 0 && r.x < b.x) ||
            (d == 1 && r.x > b.x) ||
            (d == 2 && r.y < b.y) ||
            (d == 3 && r.y > b.y)) return true;
        else return false;
    }

    // 구슬이 겹치는 경우 뒤의 구슬을 이동시킴
    public static void setOrder(Marble r, Marble b, int d, boolean redFirst) {
        switch (d) {
            case 0:
                if (redFirst) b.x++;
                else r.x++;
                break;
            case 1:
                if (redFirst) b.x--;
                else r.x--;
                break;
            case 2:
                if (redFirst) b.y++;
                else r.y++;
                break;
            case 3:
                if (redFirst) b.y--;
                else r.y--;
                break;
        }
    }

    // 겹치는거 상관없이 기울이기
    public static void move(Marble m, int d) {
        while (true) {
            int nx = m.x + dx[d];
            int ny = m.y + dy[d];

            if (board[nx][ny] == '#') break;

            m.x = nx;
            m.y = ny;

            // 구멍에 빠지는 경우 더 이상 움직이지 않음
            if (board[nx][ny] == 'O') break;
        }
    }

    public static class Marble {
        int x, y;

        public Marble(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}