[JAVA] 백준 구슬탈출 2 - 13460 ( DFS & 구현)

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

구현 + dfs 문제

 

1.  빨간 구슬과 파란 구슬은 동시에 같은 위치에 있을 수 없다.(핵심구현)

구현의 첫번째 난관이다.

 

아래처럼 방향을 정하고

int[] dx = {-1,1,0,0};
int[] dy = {0,0,-1,1};

 

기존 위치가 [x,y] 라면 다음 위치는 [ x + dx[i], y + dy[i] ]  이다. 

(이때 i는 0부터 3까지 중 하나의 숫자)

 

위치가 하나면 쉬운데 빨간 구슬과 파란 구슬의 2가지 위치를 동시에 비교해야한다.

 

다음 빨간 구슬의 위치를 nextRed 라고 하고 다음 파란 구슬의 위치를 nextBlue 라고 하자.

다음 빨간 구슬 위치와 다음 파란구슬의 위치를 구하기 위한 나의 로직은 다음과 같다.

 

 

if( 빨간 구슬도 이동할 수 있고 파란구슬고 이동할수 있다면){

    현재 빨간 구슬 위치 = nextRed 

    다음 파란 구슬 위치 = nextBlue

}

else if(빨간 구슬은 이동할 수 없고 파란구슬만 이동할 수 있다면){

    if( nextBlue 가 현재 빨간 구슬의 위치가 아니라면){

            다음 파란 구슬 위치 = nextBlue

    }

}

else if(빨간 구슬만 이동할 수 있고 파란구슬은 이동할 수 없다면){

    if( nextRed  가 현재 파란 구슬의 위치가 아니라면){

            현재 빨간 구슬 위치 = nextRed 

    }

}

 

그리고 빨간 구슬과 파란구슬이 위 로직을 거쳐도 제자리 걸음일 때까지 위 로직을 반복하면 하나의 Move가 된다.

 

 

이를 바탕으로 dfs를 통해서 최소 이동수를 갱신해주면 된다.

 

 

2. DFS  ( 핵심 알고리즘)

    public static void dfs(int[] r,int[] b,int moveCnt) {
        if(moveCnt == 11) return;
        if(r[0]==-100 && b[0]!=-100){
            answer = answer > moveCnt ? moveCnt : answer;
            return;
        }
        if(b[0] == -100) return;

        for(int i=0;i<4;i++){
            int[] curRed = {r[0],r[1]};
            int[] curBlue = {b[0],b[1]};
            move(curRed,curBlue,i);
            dfs(curRed,curBlue,moveCnt+1);
        }
    }

dfs의 파라미터를 가지고 복사해서 다음 dfs 함수에 넘겼다. 아마 이부분에서 메모리를 많이 잡아 먹는듯 하다.

 

 

전체코드)

 

import java.util.*;


class Main{
    static int n;
    static int m;
    static char[][] arr ;
    static int[] red = new int[2];
    static int[] blue = new int[2];
    static int[] goal = new int[2];
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int answer = Integer.MAX_VALUE;

    public static void solve(){
        dfs(red,blue,0);
        System.out.println(answer==Integer.MAX_VALUE?-1:answer);
    }

    public static void dfs(int[] r,int[] b,int moveCnt) {
        if(moveCnt == 11) return;
        if(r[0]==-100 && b[0]!=-100){
            answer = answer > moveCnt ? moveCnt : answer;
            return;
        }
        if(b[0] == -100) return;

        for(int i=0;i<4;i++){
            int[] curRed = {r[0],r[1]};
            int[] curBlue = {b[0],b[1]};
            move(curRed,curBlue,i);
            dfs(curRed,curBlue,moveCnt+1);
        }
    }


    public static void move(int[] r,int[] b,int dir){
        int[] curRed = new int[]{r[0],r[1]};
        int[] curBlue = new int[]{b[0],b[1]};
        while(next(curRed,curBlue,dir)){
            if(goalCheck(curRed)) {
                curRed[0] = -100;
                curRed[1] = -100;
            }
            if(goalCheck(curBlue)){
                curBlue[0] = -100;
                curBlue[1] = -100;
            }
        }
        r[0] = curRed[0];
        r[1] = curRed[1];
        b[0] = curBlue[0];
        b[1] = curBlue[1];
    }

    public static boolean goalCheck(int[] x){
        if(goal[0] == x[0] && goal[1] == x[1]) return true;
        else return false;
    }

    public static boolean checkRange(int x,int y){
        if(x<0 || x>=n || y<0 || y>=m) return false;
        else if(arr[x][y] == '#') return false;
        else return true;
    }

    public static boolean next(int[] red,int[] blue, int dir){
        int nx1,nx2,ny1,ny2;
        nx1 = red[0] + dx[dir];
        nx2 = blue[0] + dx[dir];
        ny1 = red[1] + dy[dir];
        ny2 = blue[1] + dy[dir];

        if(checkRange(nx1,ny1) && checkRange(nx2,ny2)){
            red[0] = nx1;
            red[1] = ny1;
            blue[0] = nx2;
            blue[1] = ny2;
            return true;
        }
        else if(!checkRange(nx1,ny1) && checkRange(nx2,ny2)){
            if(red[0] == nx2 && red[1] == ny2){
                return false;
            }
            else{
                blue[0] = nx2;
                blue[1] = ny2;
                return true;
            }
        }
        else if(checkRange(nx1,ny1) && !checkRange(nx2,ny2)){
            if(blue[0] == nx1 && blue[1] == ny1){
                return false;
            }
            else{
                red[0] = nx1;
                red[1] = ny1;
                return true;
            }
        }

        return false;

    }

    public static void main(String[] args){
        Scanner sc  = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new char[n][m];
        for(int i=0;i<n;i++) arr[i] = new char[m];
        for(int i =0;i<n;i++){
            char[] temp = sc.next().toCharArray();
            for(int j=0;j<m;j++){
                if(temp[j] == 'R'){
                    red[0] = i;
                    red[1] = j;
                    arr[i][j] = '.';
                }
                else if(temp[j] == 'B'){
                    blue[0] = i;
                    blue[1] = j;
                    arr[i][j] = '.';
                }
                else if(temp[j] == 'O'){
                    goal[0] = i;
                    goal[1] = j;
                    arr[i][j] = '.';
                }
                else{
                    arr[i][j] = temp[j];
                }
            }
        }

        solve();

    }

}