[BOJ 13460] 구슬 탈출 2 - JAVA, Gold1

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

13460번: 구슬 탈출 2

 

 

📌구현할 기능 목록

1. 직사각형 맵의 크기와 맵의 좌표별 위치 정보를 입력받는다.

  - R, B, O 값을 입력받았을 경우, 해당 좌표값을 별도의 배열에 저장한다.

 

2. 1~10번 기울여 이동하여 조건에 만족하는 결과가 나오도록 DFS 함수를 구현한다.

  - 한번의 테스트 케이스를 마치면, 맵 정보와 빨간공, 파란공의 위치 좌표를 초기화하는 함수를 작동시킨다.

 

3. 특정 방향으로 기울일 경우 빨간공과 파란공이 이동할 수 없을 때까지 이동하는 함수를 작성한다.

  - 이동 방향에 따라 빨간공 또는 파란공의 이동 우선순위를 구분하여 이동시킨다.

    - 예로 위쪽으로 직사각형을 기울인 경우, 만약 빨간공이 파란공보다 더 위에 존재한다면

      빨간공을 파란공보다 먼저 이동시킨 후 파란공을 이동시킨다.(파란공이 더 위에 있다면 파란공부터 이동)

  - 파란공이 목적지에 도달하면 해당 이동은 어떠한 경우에도 실패이다.

  - 이동할 수 없을때 까지 특정 방향으로 한칸 씩 계속해서 이동한다

  - 위 조건들이 만족하는 상태에서 빨간공이 목적지에 도달하면 성공 조건을 만족한다.

 

4. 조건을 성공적으로 만족하는 최소의 이동횟수를 출력하고 프로그램을 종료시킨다.

  - 조건을 만족하는 경우의 수가 없다면 -1을 출력한다.

 

🛠주요 로직

직사각형을 기울였을 때, 공들이 방향에 맞게 이동하는 함수를 작성하는 것이 문제의 핵심이다.

 

그 중 가장 실수하기 쉬운 유형은 아래와 같은 유형이다.

위 경우에서 직사각형을 왼쪽으로 기울이면 빨간공과 파란공 두개 모두가 한 번의 기울임으로 목적지에 도달하게 된다.

 

문제 조건에서 파란공이 목적지에 도달하는 경우 실패라고 명시되었으므로,

빨간공이 목적지에 도착하더라도 실패이다.

 

[위 맵을 왼쪽으로 기울인 경우 공이 이동하는 과정]

 

따라서  빨간공이 목적지에 도착하는 즉시 탈출 성공이라는 로직을 구현해서는 안 되며,

기울였을 때 모든 공의 움직임이 없을 때까지 이동 후, 파란공이 목적지에 도달하지 않았으면서

빨간공이 목적지에 도달한 경우에만 탈출 성공이라는 결과를 도출해야 한다.

 

💻코드 적용

1. 직사각형 맵의 크기와 맵의 좌표별 위치 정보를 입력받는다.

  - R, B, O 값을 입력받았을 경우, 해당 좌표값을 별도의 배열에 저장한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());

map = new char[N][M];
originMap = new char[N][M];

for(int i=0;i<N;++i){
    String tempMap = br.readLine();
    for(int j=0;j<M;++j){
        originMap[i][j]=tempMap.charAt(j);
        if(originMap[i][j]=='R'){
            originRedBallPosition[0]=i;
            originRedBallPosition[1]=j;
        }
        else if(originMap[i][j]=='B'){
            originBlueBallPosition[0]=i;
            originBlueBallPosition[1]=j;
        }
        else if(originMap[i][j]=='O'){
            goal[0]=i;
            goal[1]=j;
        }
    }
}

 

2. 1~10번 기울여 이동하여 조건에 만족하는 결과가 나오도록 DFS 함수를 구현한다.

  - 한번의 테스트 케이스를 마치면, 맵 정보와 빨간공, 파란공의 위치 좌표를 초기화하는 함수를 작동시킨다.

static void dfs(int depth){
    if(depth==maxCount){
        init();
        if(incline()){
            isSuccess=true;
        }
        return;
    }

    for(int i=0;i<4;++i){
        direction[depth]=i;
        dfs(depth+1);
    }
}

 

3. 특정 방향으로 기울일 경우 빨간공과 파란공이 이동할 수 없을 때까지 이동하는 함수를 작성한다.

  - 이동 방향에 따라 빨간공 또는 파란공의 이동 우선순위를 구분하여 이동시킨다.

    - 예로 위쪽으로 직사각형을 기울인 경우, 만약 빨간공이 파란공보다 더 위에 존재한다면

      빨간공을 파란공보다 먼저 이동시킨 후 파란공을 이동시킨다.(파란공이 더 위에 있다면 파란공부터 이동)

  - 파란공이 목적지에 도달하면 해당 이동은 어떠한 경우에도 실패이다.

  - 이동할 수 없을때 까지 특정 방향으로 한칸 씩 계속해서 이동한다

  - 위 조건들이 만족하는 상태에서 빨간공이 목적지에 도달하면 성공 조건을 만족한다.

static boolean incline(){
    boolean result=false;
    for(int i=0;i<maxCount;++i){
        if(direction[i]==0){ // 상
            if(redBallPosition[0]<blueBallPosition[0]){
                while(true){
                    int redMx = redBallPosition[0]+dx[0];
                    int blueMx = blueBallPosition[0]+dx[0];

                    if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
                    || map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
                        break;
                    }

                    if(redMx>=1 && map[redMx][redBallPosition[1]]!='#'){
                        map[redBallPosition[0]][redBallPosition[1]]='.';
                        redBallPosition[0]=redMx;
                        map[redBallPosition[0]][redBallPosition[1]]='R';
                    }

                    if(blueMx>=1 && map[blueMx][blueBallPosition[1]]!='#'){
                        map[blueBallPosition[0]][blueBallPosition[1]]='.';
                        blueBallPosition[0]=blueMx;
                        map[blueBallPosition[0]][blueBallPosition[1]]='B';
                    }

                    if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
                        map[goal[0]][goal[1]]='O';
                        result=true;
                    }

                    if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
                        return false;
                    }
                }
                if(result) return true;
            }
            else{
                while(true){
                    int redMx = redBallPosition[0]+dx[0];
                    int blueMx = blueBallPosition[0]+dx[0];

                    if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
                            || map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
                        break;
                    }

                    if(blueMx>=1 && map[blueMx][blueBallPosition[1]]!='#'){
                        map[blueBallPosition[0]][blueBallPosition[1]]='.';
                        blueBallPosition[0]=blueMx;
                        map[blueBallPosition[0]][blueBallPosition[1]]='B';
                    }

                    if(redMx>=1 && map[redMx][redBallPosition[1]]!='#'){
                        map[redBallPosition[0]][redBallPosition[1]]='.';
                        redBallPosition[0]=redMx;
                        map[redBallPosition[0]][redBallPosition[1]]='R';
                    }

                    if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
                        map[goal[0]][goal[1]]='O';
                        result=true;
                    }

                    if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
                        return false;
                    }
                }
                if(result) return true;
            }
        }
        else if(direction[i]==1){ // 우
            ...(중략)
        }
    }
}

 

직사각형을 위쪽으로 기울인 하나의 경우만을 나타냈다.

빨간공과 파란공의 위치에 따라 두 공들 중 더 위에 있는 공을 우선으로 이동시켰다.

 

4. 조건을 성공적으로 만족하는 최소의 이동횟수를 출력하고 프로그램을 종료시킨다.

  - 조건을 만족하는 경우의 수가 없다면 -1을 출력한다.

public static void main(String[] args) throws IOException {
    ...(생략)

    for(int i=1;i<=10;++i){
        maxCount=i;
        init();
        dfs(0);
        if(isSuccess){
            bw.write(maxCount+"\n");
            bw.flush();
            bw.close();
            return;
        }
    }
    bw.write("-1\n");
    bw.flush();
    bw.close();
}

 

⌨제출 코드

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

public class Main {
    static int N,M;
    static char map[][];
    static char originMap[][];
    static int maxCount=0;
    static boolean isSuccess=false;
    static int direction[] = new int[10];
    static int dx[]={-1,0,1,0}; // 상우하좌
    static int dy[]={0,1,0,-1};
    static int originRedBallPosition[] = new int[2]; // [0] -> x, [1] -> y
    static int originBlueBallPosition[] = new int[2];
    static int redBallPosition[] = new int[2]; // [0] -> x, [1] -> y
    static int blueBallPosition[] = new int[2];
    static int goal[] = new int[2];

    static boolean incline(){
        boolean result=false;
        for(int i=0;i<maxCount;++i){
            if(direction[i]==0){ // 상
                if(redBallPosition[0]<blueBallPosition[0]){
                    while(true){
                        int redMx = redBallPosition[0]+dx[0];
                        int blueMx = blueBallPosition[0]+dx[0];

                        if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
                        || map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
                            break;
                        }

                        if(redMx>=1 && map[redMx][redBallPosition[1]]!='#'){
                            map[redBallPosition[0]][redBallPosition[1]]='.';
                            redBallPosition[0]=redMx;
                            map[redBallPosition[0]][redBallPosition[1]]='R';
                        }

                        if(blueMx>=1 && map[blueMx][blueBallPosition[1]]!='#'){
                            map[blueBallPosition[0]][blueBallPosition[1]]='.';
                            blueBallPosition[0]=blueMx;
                            map[blueBallPosition[0]][blueBallPosition[1]]='B';
                        }

                        if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
                            map[goal[0]][goal[1]]='O';
                            result=true;
                        }

                        if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
                            return false;
                        }
                    }
                    if(result) return true;
                }
                else{
                    while(true){
                        int redMx = redBallPosition[0]+dx[0];
                        int blueMx = blueBallPosition[0]+dx[0];

                        if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
                                || map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
                            break;
                        }

                        if(blueMx>=1 && map[blueMx][blueBallPosition[1]]!='#'){
                            map[blueBallPosition[0]][blueBallPosition[1]]='.';
                            blueBallPosition[0]=blueMx;
                            map[blueBallPosition[0]][blueBallPosition[1]]='B';
                        }

                        if(redMx>=1 && map[redMx][redBallPosition[1]]!='#'){
                            map[redBallPosition[0]][redBallPosition[1]]='.';
                            redBallPosition[0]=redMx;
                            map[redBallPosition[0]][redBallPosition[1]]='R';
                        }

                        if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
                            map[goal[0]][goal[1]]='O';
                            result=true;
                        }

                        if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
                            return false;
                        }
                    }
                    if(result) return true;
                }
            }
            else if(direction[i]==1){ // 우
                if(redBallPosition[1]>blueBallPosition[1]){
                    while(true){
                        int redMy = redBallPosition[1]+dy[1];
                        int blueMy = blueBallPosition[1]+dy[1];

                        if(!(map[redBallPosition[0]][redMy]=='.' || map[redBallPosition[0]][redMy]=='O'
                                || map[blueBallPosition[0]][blueMy]=='.' || map[blueBallPosition[0]][blueMy]=='O')){
                            break;
                        }

                        if(redMy<M-1 && map[redBallPosition[0]][redMy]!='#'){
                            map[redBallPosition[0]][redBallPosition[1]]='.';
                            redBallPosition[1]=redMy;
                            map[redBallPosition[0]][redBallPosition[1]]='R';
                        }

                        if(blueMy<M-1 && map[blueBallPosition[0]][blueMy]!='#'){
                            map[blueBallPosition[0]][blueBallPosition[1]]='.';
                            blueBallPosition[1]=blueMy;
                            map[blueBallPosition[0]][blueBallPosition[1]]='B';
                        }

                        if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
                            map[goal[0]][goal[1]]='O';
                            result=true;
                        }

                        if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
                            return false;
                        }
                    }
                    if(result) return true;
                }
                else{
                    while(true){
                        int redMy = redBallPosition[1]+dy[1];
                        int blueMy = blueBallPosition[1]+dy[1];

//                        System.out.println(redBallPosition[0]+" "+redBallPosition[1]);
//                        System.out.println(blueBallPosition[0]+" "+blueBallPosition[1]);
//                        System.out.println("========================");
//                        System.out.println(redBallPosition[0]+" "+redMy);
//                        System.out.println(blueBallPosition[0]+" "+blueMy);
//                        System.out.println(redMy+" "+blueMy);

                        if(!(map[redBallPosition[0]][redMy]=='.' || map[redBallPosition[0]][redMy]=='O'
                                || map[blueBallPosition[0]][blueMy]=='.' || map[blueBallPosition[0]][blueMy]=='O')){
                            break;
                        }

                        if(blueMy<M-1 && map[blueBallPosition[0]][blueMy]!='#'){
                            map[blueBallPosition[0]][blueBallPosition[1]]='.';
                            blueBallPosition[1]=blueMy;
                            map[blueBallPosition[0]][blueBallPosition[1]]='B';
                        }

                        if(redMy<M-1 && map[redBallPosition[0]][redMy]!='#'){
                            map[redBallPosition[0]][redBallPosition[1]]='.';
                            redBallPosition[1]=redMy;
                            map[redBallPosition[0]][redBallPosition[1]]='R';
                        }

                        if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
                            map[goal[0]][goal[1]]='O';
                            result=true;
                        }

                        if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
                            return false;
                        }
                    }
                    if(result) return true;
                }

            }
            else if(direction[i]==2){ // 하
                if(redBallPosition[0]>blueBallPosition[0]){
                    while(true){
                        int redMx = redBallPosition[0]+dx[2];
                        int blueMx = blueBallPosition[0]+dx[2];

                        if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
                                || map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
                            break;
                        }

                        if(redMx<N-1 && map[redMx][redBallPosition[1]]!='#'){
                            map[redBallPosition[0]][redBallPosition[1]]='.';
                            redBallPosition[0]=redMx;
                            map[redBallPosition[0]][redBallPosition[1]]='R';
                        }

                        if(blueMx<N-1 && map[blueMx][blueBallPosition[1]]!='#'){
                            map[blueBallPosition[0]][blueBallPosition[1]]='.';
                            blueBallPosition[0]=blueMx;
                            map[blueBallPosition[0]][blueBallPosition[1]]='B';
                        }

                        if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
                            map[goal[0]][goal[1]]='O';
                            result=true;
                        }

                        if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
                            return false;
                        }
                    }
                    if(result) return true;
                }
                else{
                    while(true){
                        int redMx = redBallPosition[0]+dx[2];
                        int blueMx = blueBallPosition[0]+dx[2];

                        if(!(map[redMx][redBallPosition[1]]=='.' || map[redMx][redBallPosition[1]]=='O'
                                || map[blueMx][blueBallPosition[1]]=='.' || map[blueMx][blueBallPosition[1]]=='O')){
                            break;
                        }

                        if(blueMx<N-1 && map[blueMx][blueBallPosition[1]]!='#'){
                            map[blueBallPosition[0]][blueBallPosition[1]]='.';
                            blueBallPosition[0]=blueMx;
                            map[blueBallPosition[0]][blueBallPosition[1]]='B';
                        }

                        if(redMx<N-1 && map[redMx][redBallPosition[1]]!='#'){
                            map[redBallPosition[0]][redBallPosition[1]]='.';
                            redBallPosition[0]=redMx;
                            map[redBallPosition[0]][redBallPosition[1]]='R';
                        }

                        if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
                            map[goal[0]][goal[1]]='O';
                            result=true;
                        }

                        if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
                            return false;
                        }
                    }
                    if(result) return true;
                }
            }
            else if(direction[i]==3){ // 좌
                if(redBallPosition[1]<blueBallPosition[1]){
                    while(true){
                        int redMy = redBallPosition[1]+dy[3];
                        int blueMy = blueBallPosition[1]+dy[3];

                        if(!(map[redBallPosition[0]][redMy]=='.' || map[redBallPosition[0]][redMy]=='O'
                                || map[blueBallPosition[0]][blueMy]=='.' || map[blueBallPosition[0]][blueMy]=='O')){
                            break;
                        }

                        if(redMy>=1 && map[redBallPosition[0]][redMy]!='#'){
                            map[redBallPosition[0]][redBallPosition[1]]='.';
                            redBallPosition[1]=redMy;
                            map[redBallPosition[0]][redBallPosition[1]]='R';
                        }

                        if(blueMy>=1 && map[blueBallPosition[0]][blueMy]!='#'){
                            map[blueBallPosition[0]][blueBallPosition[1]]='.';
                            blueBallPosition[1]=blueMy;
                            map[blueBallPosition[0]][blueBallPosition[1]]='B';
                        }

                        if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
                            map[goal[0]][goal[1]]='O';
                            result=true;
                        }

                        if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
                            return false;
                        }
//                        printMap();
                    }
                    if(result) return true;
                }
                else{
                    while(true){
                        int redMy = redBallPosition[1]+dy[3];
                        int blueMy = blueBallPosition[1]+dy[3];

                        if(!(map[redBallPosition[0]][redMy]=='.' || map[redBallPosition[0]][redMy]=='O'
                                || map[blueBallPosition[0]][blueMy]=='.' || map[blueBallPosition[0]][blueMy]=='O')){
                            break;
                        }

                        if(blueMy>=1 && map[blueBallPosition[0]][blueMy]!='#'){
                            map[blueBallPosition[0]][blueBallPosition[1]]='.';
                            blueBallPosition[1]=blueMy;
                            map[blueBallPosition[0]][blueBallPosition[1]]='B';
                        }

                        if(redMy>=1 && map[redBallPosition[0]][redMy]!='#'){
                            map[redBallPosition[0]][redBallPosition[1]]='.';
                            redBallPosition[1]=redMy;
                            map[redBallPosition[0]][redBallPosition[1]]='R';
                        }

                        if(redBallPosition[0]==goal[0] && redBallPosition[1]==goal[1]){
                            map[goal[0]][goal[1]]='O';
                            result=true;
                        }

                        if(blueBallPosition[0]==goal[0] && blueBallPosition[1]==goal[1]){
                            return false;
                        }
                    }
                    if(result) return true;
                }
            }
//            printMap();
        }
        return result;
    }

    static void printDirection(){
        for(int i=0;i<maxCount;++i){
            System.out.print(direction[i]+" ");
        }
        System.out.println();
    }

    static void printMap(){
        System.out.println("=======================");
        for(int i=0;i<N;++i){
            for(int j=0;j<M;++j){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("=======================");
    }

    static void dfs(int depth){
        if(depth==maxCount){
            init();
            if(incline()){
                isSuccess=true;
            }
            return;
        }

        for(int i=0;i<4;++i){
            direction[depth]=i;
            dfs(depth+1);
        }
    }

    static void init(){
        for(int i=0;i<N;++i){
            map[i]=originMap[i].clone();
        }

        redBallPosition[0]=originRedBallPosition[0];
        redBallPosition[1]=originRedBallPosition[1];
        blueBallPosition[0]=originBlueBallPosition[0];
        blueBallPosition[1]=originBlueBallPosition[1];
    }

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        originMap = new char[N][M];

        for(int i=0;i<N;++i){
            String tempMap = br.readLine();
            for(int j=0;j<M;++j){
                originMap[i][j]=tempMap.charAt(j);
                if(originMap[i][j]=='R'){
                    originRedBallPosition[0]=i;
                    originRedBallPosition[1]=j;
                }
                else if(originMap[i][j]=='B'){
                    originBlueBallPosition[0]=i;
                    originBlueBallPosition[1]=j;
                }
                else if(originMap[i][j]=='O'){
                    goal[0]=i;
                    goal[1]=j;
                }
            }
        }

        for(int i=1;i<=10;++i){
            maxCount=i;
            init();
            dfs(0);
            if(isSuccess){
                bw.write(maxCount+"\n");
                bw.flush();
                bw.close();
                return;
            }
        }
        bw.write("-1\n");
        bw.flush();
        bw.close();
    }
}