[백준 13460] 구슬 탈출2(Java)

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

이 문제는 bfs를 이용하여 문제의 조건들을 하나씩 구현한다면 풀 수 있습니다.

우선 구슬을 움직이는 로직을 먼저 짜야 합니다. 구슬의 움직임의 특징은 한 방향으로 장애물이 나올때까지 계속 이동한다는 점입니다. 따라서 반복문 안에서 계속 해당 방향으로의 이동값을 증가시키면서 장애물이 나올때까지 더해서 그 결과를 출력하면 됩니다.

이 문제에서 또한 고려해야 할 점은 두 구슬이 같은 위치에 놓일 때 어떤 식으로 위치를 재조정해주어야 하는지 여부입니다. 이전에 움직인 방향에 따라 움직이기 이전의 좌표값을 비교하여 각 방향 별로 처리해주면 됩니다. 예를 틀면 오른쪽으로 이동하는 방향일 경우 움직이기 이전 x값이 더 큰 구슬은 움직인 위치 그대로 가고, x값이 더 작았던 구슬이 x-1만큼 이동하는 식으로 위치를 재조정해줍니다.

이후 문제의 조건인 10번 이하로 실행시킬 수 있도록 조정하고, 빨간 구슬이 떨어졌을 때 횟수값을 리턴하는 방식으로 문제를 풀면 되겠습니다.

다음은 코드입니다.

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

public class Main{

    static char[][] req = new char[11][11];
    static boolean[][][][] check = new boolean[11][11][11][11];
    static int N,M;
    static int hy,hx;
    static Marble red;
    static Marble blue;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};

    static Marble moveMarble(Marble marble, int dir){
        int y = marble.y;
        int x = marble.x;

        while(req[y+dy[dir]][x+dx[dir]] != '#'){
            y += dy[dir];
            x += dx[dir];
            if(y == hy && x == hx) break;
        }

        return new Marble(y,x);
    }

    static int bfs(){
        check[blue.y][blue.x][red.y][red.x] = true;
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(blue,red,0));

        while(!queue.isEmpty()){
            Pair marbles = queue.poll();

            // 10번 이하로 움직여서 구슬을 빼낼 수 없으면 카운트 제외
            if(marbles.cnt>10) return -1;

            // 빨간 구슬이 빠질 경우 res에 넣기
            if(marbles.red.y==hy && marbles.red.x==hx) return marbles.cnt;

            for(int i=0;i<4;i++){
                Marble new_blue = moveMarble(marbles.blue,i);
                Marble new_red = moveMarble(marbles.red,i);

                // 파란 구슬이 빠질 경우 무조건 실패
                if(new_blue.y==hy && new_blue.x==hx) continue;

                // 두 구슬의 위치가 같은 경우 재조정
                if(new_blue.y== new_red.y && new_blue.x== new_red.x){
                    switch (i){
                        // 오른쪽
                        case 0:
                            //  움직이기 이전 x값이 더 큰 구슬이 현재 위치,
                            // x값이 더 작은 구슬이 x-1만큼
                            if(marbles.blue.x > marbles.red.x) new_red.x--;
                            else new_blue.x--;
                            break;
                        // 아래쪽
                        case 1:
                            //  움직이기 이전 y값이 더 큰 구슬이 현재 위치,
                            // y값이 더 작은 구슬이 y-1만큼
                            if(marbles.blue.y > marbles.red.y) new_red.y--;
                            else new_blue.y--;
                            break;
                        // 왼쪽
                        case 2:
                            //  움직이기 이전 x값이 더 작은 구슬이 현재 위치,
                            // x값이 더 큰 구슬이 x+1만큼
                            if(marbles.blue.x > marbles.red.x) new_blue.x++;
                            else new_red.x++;
                            break;
                        // 위쪽
                        case 3:
                            //  움직이기 이전 y값이 더 작은 구슬이 현재 위치,
                            // y값이 더 큰 구슬이 y+1만큼
                            if(marbles.blue.y > marbles.red.y) new_blue.y++;
                            else new_red.y++;
                            break;
                    }
                }

                // 이미 굴린 적 없는 포지션이었다면 이어서 구슬 굴리기
                if(!check[new_blue.y][new_blue.x][new_red.y][new_red.x]){
                    check[new_blue.y][new_blue.x][new_red.y][new_red.x] = true;
                    queue.add(new Pair(new_blue,new_red, marbles.cnt+1));
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;i++){
            String str = br.readLine();

            for(int j=0;j<M;j++){
                req[i][j] = str.charAt(j);
                if(req[i][j]=='B') blue = new Marble(i,j);
                else if(req[i][j]=='R') red = new Marble(i,j);
                else if(req[i][j]=='O'){
                    hy = i;
                    hx = j;
                }
            }
        }

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

class Marble{
    int y;
    int x;

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

class Pair{
    Marble blue;
    Marble red;
    int cnt;

    public Pair(Marble blue, Marble red, int cnt){
        this.blue = blue;
        this.red = red;
        this.cnt = cnt;
    }
}