[백준] 13460번 구슬 탈출2

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/swtest/Q13460.java

구슬 두개 R, B 그리고 구슬이 다닐수 있는 통로 '.'가 주어진다.
구슬이 다닐 수 없는 통로는 '#'로 주어지며, 맵의 외곽은 '#'로 이루어져있다.
구슬이 빠질 수 있는 구멍은 'O'로 이루어져있다. 구슬은 맵을 상 하 좌 우로 기울여서 이동이 가능하다. 
맵을 기울여 구슬들을 이동시킬 때, R구슬만 구멍에 빠질 때 까지 몇 번을 기울였는지 최소값을 출력하여라.
R 구슬이 빠질 때 B구슬 빠진 경우는 실패다. 최대 10번까지 기울일 수 있다.
불가능한 경우 -1을 출력한다.

처음 생각

어떻게 기울였을 때, 구슬을 빼낼 수 있을것인가를 생각해 봐야한다. 정답은 모른다이다. 예제가 보이지도 않으니깐 진짜 모른다! 즉, 최대 10개의 경우에 모든 경우의 수를 체크해 봐야한다는 것이다. DFS를 이용해서 10개의 경우의 수를 만들어 주었다.

▶ DFS 깊이를 10까지 가도록 하고, 한 번의 DFS 마다 반복문으로 체크 배열에 상(0) 하(1) 좌(2) 우(3)를 넣어주면서 진행하였다.

다음 생각

다음으로 생각해 본것은 두 개의 구슬이라는 점이다. 한 번 기울였을 때, R과 B 구슬 둘 다 이동시켜야 한다. 

▶ Queue의 타입으로 만든 inner class Pair가 둘의 x,y값을 다 저장할 수 있도록 구현해 주었다.

다다음 생각

DFS를 통해 10개의 상 하 좌 우 순서가 정해지면 해당 방향을 가지고 기울여 주는 lean() 메소드를 호출해 주었다.

▶ 매번 그러했듯 호출전에 원래 배열을 복사한 copy 배열을 원래 배열로 초기화 시켜주었다.

다다다음 생각

해당 방향으로 기울였을 때, 만약 같은 줄에 있다면 어떤게 앞에있는지를 생각해주어야 한다. #  R  B 가 있을 때 왼쪽으로 기울이면 #RB가 되어야 하기 때문이다. 하지만 오른쪽으로 기울여주면 오른쪽 벽으로 RB#의 순서로 쌓일 것이다. 이런걸 모르기 때문에 일단 빨간 구슬을 먼저 이동시켜 준 뒤, 파란 구슬을 이동시켜 주었다.

▶ 빨간 구슬을 먼저 이동시키고, 맵에 'B'로 표시된 파란 구슬을 만난다면 boolean 변수 flagRB를 true로 바꿔주었다. 이 후 파란 구슬을 이동시키기 전에 이 flag가 true라면 파란 구슬이 빨간 구슬보다 앞에 있어야하므로 현 좌표에서 해당 방향으로 한 칸 뒤로 옮겨주었다.

▶ 다음으로 파란 구슬이 이동시킨다. 이동 중 빨간 구슬을 만난다면 boolean flagBR을 true로 바꿔주었다. 이동이 끝나고 만약 flagBR이 true이고 앞선 빨간 구슬이 파란구슬을 만난 변수 flagRB가 false라면 파란 구슬을 한 칸 뒤로 이동시켜주었다.(빨간 구슬이 파란 구슬을 만났다는 판단이 true이면 먼저 이동했으니 빨간 구슬이 뒤였다는 말이지만 나중에 이동시킨 파란 구슬은 만났다는 판단이 true여도 빨간 구슬 변수가 true이면 파란 구슬이 뒤였다는 말이므로 빨간 구슬 변수가 false일 경우 파란 구슬의 위치를 한 칸 뒤로 바꿔준다.)

다다다다음 생각

위의 경우에서 빨간 구슬이 'O'를 만나 구멍이 들어갔다면, 또 다른 boolean 변수 flagR을 true로 바꿔주었다. 마찬가지로 파란 구슬도 구멍에 들어갔다면 boolean 변수 flagB를 true로 바꿔주었다. 둘 다 이동시킨 후, flagB가 true라면 바로 이 케이스는 안된다는 false를 return 해 주고, 이를 지나가고 flagR이 true라면 true를 return해서 현재 기울인 횟수를 전체 구하는 값과 비교해주어 최소값을 구하였다.

▶ 현 기울임을 시작할 때 시작 좌표를 '.'로 바꿔주고 이동후 좌표를 'R'과 'B'로 바꿔준 후, 바뀐 좌표를 새로운 R과 B의 좌표라고 바꿔준 후 메소드를 종료하였다.

방안

1) DFS를 통해 경우의 수를 만들어 주는 경우 10개의 케이스를 만들 때, 왼,왼,왼,왼,왼,왼,왼,왼,왼,왼 같이 한 쪽 기울임이 연속적으로 나오면 구슬은 변하는 것 없이 계속 똑같은 위치에 있게된다. 따라서 DFS 메소드 solve의 매개변수로 이전에 어떤 움직임을 했나를 만들어주어서 다음번 방향을 정할 때 이전 값과 같은 값이 들어가지 않도록 해주었다.

package baekjoon.swtest;
 
import java.util.Scanner;
 
public class Q13460 {
    static int n,m;
    static int[][] arr;
    static Pair t,t2;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 세로 크기
        m = sc.nextInt(); // 가로 크기
        arr = new int[n][m]; // 원 배열
        copy = new int[n][m]; // 복사 배열
        t = new Pair(0, 0, 0, 0); // R B의 최초값
        t2 = new Pair(0, 0, 0, 0); // 케이스를 진행할 때 R B의 좌표값
        for(int i=0;i<n;i++) {
            String str = sc.next();
            for(int j=0;j<m;j++) {
                arr[i][j]= str.charAt(j);
                // R 과 B의 위치 받기
                if(arr[i][j]=='R') {
                    t.rx = i; t.ry = j;
                }else if(arr[i][j]=='B'){
                    t.bx = i; t.by = j;
                }
            }
        }
        // 움직이는 조합을 모두 만들어 주자.
        solve(0,-1);
        if(result==11) result=-1;
        System.out.println(result);
    }
    
    static int[][] copy;
    private static void init() {
        // R B 위치 초기화
        t2.rx = t.rx; t2.ry = t.ry;
        t2.bx = t.bx; t2.by = t.by;
        end = false; // 게임끝 초기화
        // 맵  복사
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) 
                copy[i][j] = arr[i][j];
        }
    }
    
    // 하 우 상 좌
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static boolean lean(int d) {
        int rx=t2.rx, ry=t2.ry, bx=t2.bx, by=t2.by;
        // R 출구 체크, RB R이 이동중 B를 만났나(만난것은 한 칸 뒤로 옮기도록)
        boolean flagR=false,flagRB=false,
                flagBR=false,flagB=false;
        // 빨강 먼저 이동
        while(true) {
            rx = rx+dir[d][0]; ry = ry+dir[d][1];
            // 길외에 것을 만난다면
            if(copy[rx][ry]!='.') {
                // 출구 일경우
                if(copy[rx][ry]=='O')
                    flagR=true; // R 나감 체크
                else if(copy[rx][ry]=='B') {
                    flagRB = true; // B 만남 체크
                    continue; // B일경우 일단 쭉 간다.
                }
                // # 이므로 한 칸 뒤로 물려주기
                rx = rx-dir[d][0]; ry = ry-dir[d][1];
                break;
            }
        }
        // R이 움직이다 B를 만났다면 R이 한 칸뒤로 움직여야한다.
        if(flagRB) {
            rx = rx-dir[d][0];
            ry = ry-dir[d][1];
        }
        // 파랑 이동
        while(true) {
            bx = bx+dir[d][0]; by = by+dir[d][1];
            // 길외에 것을 만난다면
            if(copy[bx][by]!='.') {
                // 출구 일경우
                if(copy[bx][by]=='O')
                    flagB=true; // B 나감 체크
                else if(copy[bx][by]=='R') {
                    flagBR = true; // R 만남 체크
                    continue; // R일경우 일단 쭉 간다.
                }
                // # 이므로 한 칸 뒤로 물려주기
                bx = bx-dir[d][0]; by = by-dir[d][1];
                break;
            }
        }
        // R은 만나지 않았고, B가 움직이다 R을 만났다면  
        if(!flagRB && flagBR) {
            bx = bx-dir[d][0];
            by = by-dir[d][1];
        }
        
        // B가 끝났다면 false
        if(flagB) {
            end = true; // 게임 끝
            return false;
        }
        // R이 끝났다면 true
        if(flagR) return true;
        
        // 바뀐 값들 넣어주기
        copy[t2.rx][t2.ry]='.';
        copy[rx][ry] = 'R';
        copy[t2.bx][t2.by]='.';
        copy[bx][by] = 'B';
        
        // 시작값 바꿔주기
        t2.rx=rx; t2.ry=ry;
        t2.bx=bx; t2.by=by;
        return false;
    }
    
    // 최대 10이므로 11로 지정
    static int result=11;
    static boolean end;
    static int[] visited = new int[10];
    private static void solve(int idx,int prev) {
        // 10가지의 모든 방향이 만들어졌으면
        if(idx==10) {
            // 그 방향들 가지고 체크하기
            init(); // copy 배열 초기화
            for(int i=0;i<10;i++) {
                if(result<=i+1) return;
                if(lean(visited[i])) {
                    // true라면 게임 끝. 이태까지 횟수 최소 구하기
                    result = Math.min(result, i+1);
                    return;
                }
                // 게임이 끝났다면 바로 끝
                if(end) break;
            }
            return;
        }
        
        // 연속적으로 같은 방향으로의 동작을 할 필요는 없다.
        for(int i=0;i<4;i++) {
            if(i==prev) continue;
            visited[idx] = i;
            solve(idx+1,i);
        }
    }
    
    static class Pair{
        int rx,ry,bx,by;
        Pair(int rx,int ry,int bx,int by){
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
        }
    }
}