구슬 탈출

📍 문제 설명

💡 접근

구슬이 동시에 움직여야하고 제약 사항이 꽤 있었기때문에 많이 까다로운 문제였다.

두 구슬의 방문여부를 각각 체크 해주기위해서 4차원 배열을 사용해야 했다.

1.파란 구슬과 빨간 구슬을 동시에 기울이고

2.상하좌우로 기울이는데, 다음칸이 벽이 아니고 현재 칸이 구멍이 아니라면 계속 움직인다.

3.구슬이 같은 칸에 있을 경우에는 뒤에서 온 구슬을 먼저온 구슬 뒤에 배치시킨다.

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, h, k, answer,cnt, max, L, R, C;
    static char[][] board, dis;
    static boolean[][][][] visited;
    static int[] ch,pm, combi;
    static boolean flag = true;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();
        kb.nextLine();
        board = new char[n][m];

        int rx = 0,ry = 0,bx = 0,by = 0;
        for(int i = 0; i < n; i++) {
            String s = kb.nextLine();
            for(int j = 0; j < m; j++) {
                board[i][j] = s.charAt(j);
                if(board[i][j] == 'B') {
                    bx = i; by = j;
                }
                else if(board[i][j] == 'R') {
                    rx = i; ry = j;
                }
            }
        }

        //'.' 빈 칸
        //'#' 이동할 수 없는 장애물
        //'O' 구멍의 위치
        //'R' 빨간 구슬의 위치
        //'B' 파란 구슬의 위치

        //빨간 공과 파란 구슬은 동시에 움직인다.
        //벽을 만나는 마지막 지점으로 움직인다.
        //예제 1 - 오른쪽으로 한번 기울이면 된다.
        //예제 2 - 왼쪽, 아래, 오른쪽, 아래, 왼쪽으로 움직이면 된다.
        //예제 3 - 왼쪽, 아래, 오른쪽, 아래, 왼쪽으로 움직이면 된다.
        //예제 4 - 아래, 오른쪽, 위, 오른쪽, 아래, 왼쪽, 아래, 오른쪽, 위, 오른쪽, 아래, 오른쪽으로 움직이면 되지만 10번 초과해서 못간다.
        //예제 5 - 오른쪽으로 한번 기울이면 된다.
        //예제 6 - 아래, 오른쪽, 위, 오른쪽 ,아래, 왼쪽, 아래로 가면 된다.
        //예제 7 - 왼쪽으로 기울이면 빨강공이 빠지지만 파랑공도 빠져버리므로 안된다.

        //시작 지점은 R과 B의 위치 & 그리고 서로 같은 칸에 있을 수 없다.
        System.out.println(T.solution(rx ,ry, bx, by));

    }

    private int solution(int rx, int ry, int bx, int by) {
        Queue<Turn> q = new LinkedList<>();
        //구슬 기울인 횟수
        int cnt = 1;
        //두 구슬 좌표 큐에 넣어놓기
        q.offer(new Turn(rx, ry, bx, by));
        //구슬들의 좌표 방문 여부
        visited = new boolean[n][m][n][m];
        visited[rx][ry][bx][by] = true;

        //구슬 기울이기
        while(!q.isEmpty()) {
            int len = q. size();
            for(int i = 0; i < len; i++) {
                Turn cur = q.poll();
                //해당 좌표에서 기울이기
                for(int j = 0; j < 4; j++) {
                    int cRx = cur.rx;
                    int cRy = cur.ry;
                    int cBx = cur.bx;
                    int cBy = cur.by;
                    int redDist = 0, blueDist = 0;
                    //다음 칸이 벽이 아니고 현재 칸이 구멍이 아니면 계속 이동(빨간 구슬)
                    while(board[cRx+dx[j]][cRy+dy[j]] != '#' && board[cRx][cRy] != 'O') {
                        cRx += dx[j];
                        cRy += dy[j];
                        redDist++;
                    }
                    //다음 칸이 벽이 아니고 현재 칸이 구멍이 아니면 계속 이동(파란 구슬)
                    while(board[cBx+dx[j]][cBy+dy[j]] != '#' && board[cBx][cBy] != 'O') {
                        cBx += dx[j];
                        cBy += dy[j];
                        blueDist++;
                    }
                   //파란 구슬이 빠져버렸으면 실패
                   if(board[cBx][cBy] == 'O') continue;
                   //빨간 구슬이 빠졌으면 성공
                    if(board[cRx][cRy] == 'O') return 1;

                    //빨간 구슬과 파란 구슬이 겹쳐있을 때는 이동 거리에 따라 뒤에 놓기
                    if(cRx == cBx && cRy == cBy) {
                        //빨간 구슬이 더 많이 이동한거면 파란 구슬보다 뒤에 있었다는 의미다.
                        if(redDist > blueDist) {
                            cRx -= dx[j];
                            cRy -= dy[j];
                        }else {
                            cBx -= dx[j];
                            cBy -= dy[j];
                        }
                    }

                    //이미 이동 했던 좌표면 큐에 넣어볼 필요 없음
                    if(visited[cRx][cRy][cBx][cBy]) continue;
                    visited[cRx][cRy][cBx][cBy] = true;
                    //큐에 해당 좌표 추가
                    q.offer(new Turn(cRx, cRy, cBx, cBy));
                }
            }
            if(++cnt > 10) return 0;
        }
        return 0;
    }

    private static class Turn {
        private int rx;
        private int ry;
        private int bx;
        private int by;

        public Turn(int rx, int ry, int bx, int by) {
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
        }

        @Override
        public String toString() {
            return "Turn{" +
                    "rx=" + rx +
                    ", ry=" + ry +
                    ", bx=" + bx +
                    ", by=" + by +
                    '}';
        }
    }
}