[BOJ] 백준 [13460] 구슬탈출2 JAVA

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

📝문제

📝풀이

구슬을 이동시키다가 빨간색 구슬만 구멍에 빠지는 최소 move 카운트를 return 하는 문제이다
우선 최소 횟수는 좌표 BFS 특성상 먼저 끝내는 것이 최소 횟수 이므로 종결조건을 만족하기만 하면 return

1. 총 4방향 {아래, 위, 오른, 왼} 으로 움직이는데 벽인 '#' 기호를 만날 때 까지 움직인다

2. 파란색 구슬의 좌표 nextB(X,Y) 가 구멍에 빠지면 continue 
2-1. 빨간색구슬 nextR(X,Y) 가 빠지면 move 카운트 return

3. 두 개의 구슬 좌표가 겹칠 경우 => 움직인 방향에 따라서 원래 구슬위치 기준으로 1 만큼 조정

4. 조정 된 위치가 처음 방문하는 좌표이면 큐에 Push   

import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;

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


public class Main {

    static char[][] map;
    static int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0}; // 아래, 위, 오른, 왼
    static int w, h;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        h = input[0];
        w = input[1];

        map = new char[h][w];
        Board board = new Board();

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

                switch (map[i][j]) {
                    case 'R' -> board.red = (new Point(j, i));
                    case 'B' -> board.blue = (new Point(j, i));
                    case 'O' -> Board.hole = (new Point(j, i));
                }
            }
        }//end input

        int bfs = bfs(board);
        System.out.println(bfs);
    }

    static int bfs(Board board) {

        boolean[][][][] visit = new boolean[h][w][h][w];

        LinkedList<Board> q = new LinkedList<>();
        q.add(board);
        visit[board.red.y][board.red.x][board.blue.y][board.blue.x] = true;

        while (!q.isEmpty()) {

            Board curBoard = q.poll();

            if (curBoard.move > 9) break; // 종결조건

            for (int i = 0; i < dx.length; i++) {

                int nextRX = curBoard.red.x;
                int nextRY = curBoard.red.y;
                int nextBX = curBoard.blue.x;
                int nextBY = curBoard.blue.y;

                while (isRange(nextRX + dx[i], nextRY + dy[i])) { // 빨간색 구슬 이동
                    nextRX += dx[i];
                    nextRY += dy[i];

                    if (nextRX == Board.hole.x && nextRY == Board.hole.y)
                        break;
                }

                while (isRange(nextBX + dx[i], nextBY + dy[i])) { // 파란색 구슬 이동
                    nextBX += dx[i];
                    nextBY += dy[i];

                    if (nextBX == Board.hole.x && nextBY == Board.hole.y)
                        break;
                }

                if (Board.hole.x == nextBX && Board.hole.y == nextBY)
                    continue;
                if (Board.hole.x == nextRX && Board.hole.y == nextRY) // 빨간색만 빠진경우 종료
                    return curBoard.move + 1;

                //dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
                if (nextRX == nextBX && nextRY == nextBY) { // 위치가 겹칠 경우 조정

                    switch (i) {
                        case 0 -> {
                            if (curBoard.red.y > curBoard.blue.y) nextBY -= 1;
                            else nextRY -= 1;
                        }
                        case 1 -> {
                            if (curBoard.red.y < curBoard.blue.y) nextBY += 1;
                            else nextRY += 1;
                        }
                        case 2 -> {
                            if (curBoard.red.x > curBoard.blue.x) nextBX -= 1;
                            else nextRX -= 1;
                        }
                        case 3 -> {
                            if (curBoard.red.x < curBoard.blue.x) nextBX += 1;
                            else nextRX += 1;
                        }
                    }
                }

                if (!visit[nextRY][nextRX][nextBY][nextBX]) { // 각 구슬의 위치가 처음 기록되는 경우만 push
                    visit[nextRY][nextRX][nextBY][nextBX] = true;
                    q.add(new Board(new Point(nextBX, nextBY), new Point(nextRX, nextRY), curBoard.move + 1));
                }
            }
        }
        return -1;
    }

    static boolean isRange(int x, int y) {
        return x >= 0 && y >= 0 && x < w && y < h && map[y][x] != '#';
    }
    static class Point {
        int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Board {

        Point blue, red;
        static Point hole;
        int move;

        public Board() {
            move = 0;
        }

        public Board(Point blue, Point red, int move) {
            this.blue = blue;
            this.red = red;
            this.move = move;
        }
    }
}