두 지점이 동시에, 벽에 닿기 전 까지 움직이는 bfs (백준 13460 구슬탈출2)

특이한 bfs문제

 

핵심 로직

1. 구슬을 동시에 움직이기

2. 벽에 닿기 직전까지 최대한 움직이기

3. 빨간 구슬과, 파란 구슬이 겹치는 경우를 처리

---

1. 구슬을 동시에 움직이기

빨간공과 파란공의 좌표를 같이 가지고 있는 Marble 클래스를 만들었다.

class Marble{
    private int redRow,redCol,blueRow,blueCol;

    public Marble(){}

    public Marble(int redRow, int redCol, int blueRow, int blueCol){
        this.redRow = redRow;
        this.redCol = redCol;
        this.blueRow = blueRow;
        this.blueCol = blueCol;
    }

    public int getRedRow(){
        return this.redRow;
    }
    public int getRedCol(){
        return this.redCol;
    }
    public int getBlueRow(){
        return this.blueRow;
    }
    public int getBlueCol(){
        return this.blueCol;
    }
    public void setRedRow(int row){
        this.redRow = row;
    }
    public void setRedCol(int col){
        this.redCol = col;
    }
    public void setBlueRow(int row){
        this.blueRow = row;
    }
    public void setBlueCol(int col){
        this.blueCol = col;
    }

}

 

2. 벽에 닿기 직전까지 최대한 움직이기

현재 방향으로 최대한 움직이록  while(true)문을 활용했다.

for(int d=0;d<4;d++){
                    int nextRedRow = curRedRow + dr[d];
                    int nextRedCol = curRedCol + dc[d];
                    int nextBlueRow = curBlueRow + dr[d];
                    int nextBlueCol = curBlueCol + dc[d];

                    while(true){ // 벽에 닿기 직전까지 움직이기 위해서
                        if(arr[nextRedRow][nextRedCol].equals("#")){ // 벽이랑 겹치면
                            nextRedRow -= dr[d]; // 한칸 직전 위치로 옮기기
                            nextRedCol -= dc[d]; // 한칸 직전 위치로 옮기기
                            break;
                        }

                        if(arr[nextRedRow][nextRedCol].equals("O")){ // 구멍에 빠지면 더 이상 움직일 필요가 없음
                            break;
                        }
                        nextRedRow += dr[d]; // 현재 방향(d)로 계속 움직이기
                        nextRedCol += dc[d];// 현재 방향(d)로 계속 움직이기
                    }

                    while(true){
                        if(arr[nextBlueRow][nextBlueCol].equals("#")){ // 벽이랑 겹치면
                            nextBlueRow -= dr[d]; // 한칸 직전 위치로 옮기기
                            nextBlueCol -= dc[d]; // 한칸 직전 위치로 옮기기
                            break;
                        }
                        if(arr[nextBlueRow][nextBlueCol].equals("O")){ // 구멍에 빠지면 더 이상 움직일 필요가 없음
                            break;
                        }
                        nextBlueRow += dr[d]; // 현재 방향(d)로 계속 움직이기
                        nextBlueCol += dc[d]; // 현재 방향(d)로 계속 움직이기
                    }
                    
                    ...
}

while(true)안에서 벽과 구슬의 좌표가 겹치면, 한칸 직전위치로 움직여 줬고.

구멍에 빠지면 더 이상 움직일 수가 없으니 break문으로 while(true)문을 빠져나갔다.

 

3. 빨간 구슬과, 파란 구슬이 겹치는 경우를 처리

더 먼거리를 이동한 구슬이 뒤에 출발한 구슬이다.

 

예를들어 이동 방향이 왼쪽인 경우 

👈

이동 전

이동 후

빨간공의 이동거리 : 3

파란공의 이동거리 : 4

 

더 먼거리를 이동한 파란공이 뒤에 출발한 구슬이다.

 

따라서 파란공을 직전 위치로 한 칸 움직여 줘야 한다.

위 내용을 코드로 구현

if(nextRedRow==nextBlueRow && nextRedCol==nextBlueCol){ // 빨간 구슬과 파란 구슬이 겹치는 경우
                        int redMoved = Math.abs(nextRedRow-curRedRow) + Math.abs(nextRedCol-curRedCol); // 빨간 구슬이 움직인 거리
                        int blueMoved = Math.abs(nextBlueRow-curBlueRow) + Math.abs(nextBlueCol-curBlueCol); // 파란 구슬이 움직인 거리

                        if(redMoved > blueMoved){ // 더 먼거리를 움직인 구슬이 진행 방향에서 봤을 때 뒤에서 출발한 구슬임
                            nextRedRow -= dr[d]; // 한칸 직전위치로 움직이기
                            nextRedCol -= dc[d]; // 한칸 직전위치로 움직이기
                        }else{
                            nextBlueRow -= dr[d]; // 한칸 직전위치로 움직이기
                            nextBlueCol -= dc[d]; // 한칸 직전위치로 움직이기
                        }
}

 

 

---

 

방문처리를 위해 4차원 배열을 사용, 구슬을 같이 이동, 한 칸씩 움직이는게 아닌 최대한 움직이게 한다는 점에서 새로운 bfs문제였다.

 

 

 

전체코드

package com.mincheolsong;
import java.io.*;
import java.util.*;

// 구슬(한꺼번에) 기울이기
// 이동할 때 횟수 카운트하기
// 같이 구멍에 빠지는 경우 처리

class Marble{
    private int redRow,redCol,blueRow,blueCol;

    public Marble(){}

    public Marble(int redRow, int redCol, int blueRow, int blueCol){
        this.redRow = redRow;
        this.redCol = redCol;
        this.blueRow = blueRow;
        this.blueCol = blueCol;
    }

    public int getRedRow(){
        return this.redRow;
    }
    public int getRedCol(){
        return this.redCol;
    }
    public int getBlueRow(){
        return this.blueRow;
    }
    public int getBlueCol(){
        return this.blueCol;
    }
    public void setRedRow(int row){
        this.redRow = row;
    }
    public void setRedCol(int col){
        this.redCol = col;
    }
    public void setBlueRow(int row){
        this.blueRow = row;
    }
    public void setBlueCol(int col){
        this.blueCol = col;
    }

}

public class Main {

    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,1,0,-1};
    static int N,M;
    static String[][] arr;
    static Marble marble; // 빨간공과 파란공의 좌표를 동시에 가지고 있는 Marble 객체
    static boolean[][][][] visited; // 방문처리를 위한 4차원 배열 (빨간공 row, 빨간공 col, 파란공 row, 파란공 col)

    static void solve(){
        Deque<Marble> q = new ArrayDeque();
        q.offer(marble);
        visited[marble.getRedRow()][marble.getRedCol()][marble.getBlueRow()][marble.getBlueCol()] = true;
        int count = 0;

        while(!q.isEmpty()){


            int size = q.size(); // bfs를 한 턴씩 수행하기 위해서

            for(int i=0;i<size;i++){ // 한 턴씩(size만큼) 수행
                Marble cur = q.pollFirst();

                if(arr[cur.getRedRow()][cur.getRedCol()].equals("O")){ // bfs의 특성상 처음 빨간 공이 구멍에 빠지는 경우가 최단 시간
                    System.out.println(count);
                    return;
                }

                int curRedRow = cur.getRedRow();
                int curRedCol = cur.getRedCol();
                int curBlueRow = cur.getBlueRow();
                int curBlueCol = cur.getBlueCol();

                for(int d=0;d<4;d++){
                    int nextRedRow = curRedRow + dr[d];
                    int nextRedCol = curRedCol + dc[d];
                    int nextBlueRow = curBlueRow + dr[d];
                    int nextBlueCol = curBlueCol + dc[d];

                    while(true){ // 벽에 닿기 직전까지 움직이기 위해서
                        if(arr[nextRedRow][nextRedCol].equals("#")){ // 벽이랑 겹치면
                            nextRedRow -= dr[d]; // 한칸 직전 위치로 옮기기
                            nextRedCol -= dc[d]; // 한칸 직전 위치로 옮기기
                            break;
                        }

                        if(arr[nextRedRow][nextRedCol].equals("O")){ // 구멍에 빠지면 더 이상 움직일 필요가 없음
                            break;
                        }
                        nextRedRow += dr[d]; // 현재 방향(d)로 계속 움직이기
                        nextRedCol += dc[d];// 현재 방향(d)로 계속 움직이기
                    }

                    while(true){
                        if(arr[nextBlueRow][nextBlueCol].equals("#")){ // 벽이랑 겹치면
                            nextBlueRow -= dr[d]; // 한칸 직전 위치로 옮기기
                            nextBlueCol -= dc[d]; // 한칸 직전 위치로 옮기기
                            break;
                        }
                        if(arr[nextBlueRow][nextBlueCol].equals("O")){ // 구멍에 빠지면 더 이상 움직일 필요가 없음
                            break;
                        }
                        nextBlueRow += dr[d]; // 현재 방향(d)로 계속 움직이기
                        nextBlueCol += dc[d]; // 현재 방향(d)로 계속 움직이기
                    }

                    if(arr[nextBlueRow][nextBlueCol].equals("O")){ // 만약 파란 구슬이 구멍에 빠지는 경우는 잘못된 경우. 큐에 넣지 않는다.
                        continue;
                    }

                    if(nextRedRow==nextBlueRow && nextRedCol==nextBlueCol){ // 빨간 구슬과 파란 구슬이 겹치는 경우
                        int redMoved = Math.abs(nextRedRow-curRedRow) + Math.abs(nextRedCol-curRedCol); // 빨간 구슬이 움직인 거리
                        int blueMoved = Math.abs(nextBlueRow-curBlueRow) + Math.abs(nextBlueCol-curBlueCol); // 파란 구슬이 움직인 거리

                        if(redMoved > blueMoved){ // 더 먼거리를 움직인 구슬이 진행 방향에서 봤을 때 뒤에서 출발한 구슬임
                            nextRedRow -= dr[d]; // 한칸 직전위치로 움직이기
                            nextRedCol -= dc[d]; // 한칸 직전위치로 움직이기
                        }else{
                            nextBlueRow -= dr[d]; // 한칸 직전위치로 움직이기
                            nextBlueCol -= dc[d]; // 한칸 직전위치로 움직이기
                        }
                    }
                    if(!visited[nextRedRow][nextRedCol][nextBlueRow][nextBlueCol]) { // 이미 방문했던 (빨간공row, 빨간공col, 파란공row, 파란공col) 위치가 아닐 경우에만
                        q.offer(new Marble(nextRedRow, nextRedCol, nextBlueRow, nextBlueCol)); // 큐에 넣고
                        visited[nextRedRow][nextRedCol][nextBlueRow][nextBlueCol] = true; // 방문 처리
                    }
                }
            }

            count+=1; // 움직인 횟수 카운트

            if(count==11){ // 11번 움직인 경우라면, 빼낼 수 없는 경우
                System.out.println(-1);
                return;
            }
        }

        System.out.println(-1); // 최대한 움직인 횟수가 11번 미만이고, 구멍으로 빼내지 못했으면 -1출력
    }


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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new String[N][M];

        marble = new Marble();
        visited = new boolean[N][M][N][M];

        for(int i=0;i<N;i++){
            String input = br.readLine();
            int j=0;
            for(char ch : input.toCharArray()){
                arr[i][j] = ch + "";
                if(arr[i][j].equals("R")){
                    marble.setRedRow(i);
                    marble.setRedCol(j);
                }else if(arr[i][j].equals("B")){
                    marble.setBlueRow(i);
                    marble.setBlueCol(j);
                }
                j+=1;
            }
        }

        solve();






    }

}