[백준] Q13460 구슬탈출2 JAVA

https://www.acmicpc.net/status?user_id=pcrmcw0486&problem_id=13460&from_mine=1 

채점 현황

 

삼성문제집 (1/45)

 

1. 문제 유형과 이해

그래프 탐색, 구현

빨간공과 파란공 그리고 홀이 들어있는 보드를 움직여 공을 빼보자.

보드는 상하좌우로만 움직일 수 있고, 한번 기울인다면 모든 움직임이 멈출 때 까지 유지한다.

이때, 빨간공이 파란공보다 먼저 빠져나와야한다.

최소 몇 번의 움직임으로 빨간 구슬만 빼낼 수 있을까?

 

2. 문제 접근 방법

먼저 상황을 보자.

상하좌우 4방향에 대해 구슬들이 '동시'에 움직인다.

하지만 우리는 하나씩 하나씩 옮겨줄수밖에 없게 되는데, 그렇다면 여기서 중요한 포인트는

'무엇을 먼저' 움직일 것이냐이다.

 

왼쪽으로 움직이려면 가장 왼쪽에 있는 것 부터 움직이기 시작해야하고, 

위로 움직이려면 가장 윗쪽부터 옮겨주는 것이 순서에 맞다.

 

이부분을 getPriority(redball, blueBall)을 통해서 boolean 값을 리턴받았다.

 

"누가 움직일지"가 정해졌다면, "어떻게" 움직여야 할지를 정해야한다.

움직임은 움직임이 멈출 때 까지, 유지한다고 하였으므로 갈수 있는 최대한의 방향으로 가면된다.

이 때, 중요한 점은 다음과 같다.

 - 벽에 닿으면 멈춘다.

 - 다른 공과 겹칠 수 없다.

 - 홀을 만나면 빠진다.

이 부분을 유의하면서 조건을 만족하는 동안 방향으로 계속 움직여 주면 된다.

하지만 여기서 '홀을 만나면 빠진다'라는 조건과 '다른 공과 겹칠 수 없다'라는 조건이 만나는 경우가 있는데,

동시에 홀에 빠질 수 있기 때문에 이 부분을 가장 유의하여야 한다.

 

종료조건을 확인해보자.

종료조건에 따라 이동부분이 달라질 수 있는데,

1. 파란공이 빠져나갔다. -> continue

2. 빨간공이 빠져나갔다..

 2.1 파란공도 빠져나갔다. -> answer =-1

 2.2 파란공은 못 빠져나갔다. -> answer

(빠져나갔다 의 의미는 공의 위치가 '홀'에 위치해있다는 점으로 판단한다)

 

파란공이 빠져나갔을 경우 바로 break를 통해 탈출하게 되면 다른 상태에서 갈 수 도 있는 상황을 체크할 수가 없어

continue를 해주는 것이 핵심인 것 같다.

2-1의 경우 1번 조건을 먼저 체크해주면 굳이 체크해주지 않아도 가능하다.

 

package SAMSUNG.boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
/**
 * @문제번호 : Q13460
 * @문제이름 : 구슬탈출 2
 * @난이도 : Gold I
 * @date : 2022-02-11 오후 1:41
 * @author : pcrmcw0486
 * @문제이해
 * 빨간 구슬과 파란 구슬이 보드 안에 있는데 움직여서 구멍에 맞춰 빼내야함
 * 게임의 목표는 "빨간 구슬을 구멍을 통해 빼내는 것"
 *  단, "파란 구슬이 구멍에 들어가면 안됨"
 * 왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울인다. 공은 동시에 움직인다.
 * 파란 구슬이 구멍에 빠지면 실패 동시에 빠져도 실패
 * 기울이는 동작은 더이상 구슬이 움직이지 않을 때 까지.
 * "최소 몇 번 만에 빨간 구슬이 구멍을 통해 나올 수 있을까?"
 * 10번이하로 빼내지 못하면 -1
 * @알고리즘
 * 그래프 탐색
 * @접근방법
 * 여러 조건이 있음
 * 방향을 각 step 마다 4번씩 돌려보아야함.
 * 각 step마다 방향을 움직일때, 무엇을 먼저 움직일지 정해야함. 그리고 같이 움직여야함.
 * 하나의 상태는 다음을 포함해야함
 *  (빨간 공) (파란 공) (현재까지의 스텝) (그 전 방향?) 다시 반대로 갈 필요는 없으니깡.
 *   도착했을 때 blue도 끝까지 갈수있는지 확인해봐야함.
 *   ** 움직이는 순서 정하기 **
 *   빨강이냐 파랑이냐 먼저 정해야함..
 *   순서를 제대로 정하면 될거같음.

*/
public class Main {
    static class Point{
        int x, y;
        Point(int x, int y) {
            this.x =x;
            this.y =y;
        }
    }
    static class Status{
        Point red;
        Point blue;
       // int prevDir;
        int step;
        public Status(Point red, Point blue, int step) {
            this.red = red;
            this.blue = blue;
           // this.prevDir = prevDir;
            this.step = step;
        }
    }
    static char[][] map;
    static int[][] dir = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        boolean[][][][] visited = new boolean[N][M][N][M];
        Point red = null;
        Point blue = null;
        for(int i =0;i<N;i++){
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                char c = line.charAt(j);
                map[i][j] = c;
                if(c=='R'){
                    red = new Point(i,j);
                }if(c=='B'){
                    blue= new Point(i,j);
                }
            }
        }

        Status status = new Status(red, blue, 0);
        Queue<Status> queue = new LinkedList<>();
        queue.add(status);
        visited[red.x][red.y][blue.x][blue.y] = true;
        int ans = -1;
        
        //BFS
        while(!queue.isEmpty()){
            Status cur = queue.poll();
            if(cur.step>10) break;
            if(map[cur.blue.x][cur.blue.y]=='O') continue;
            if (map[cur.red.x][cur.red.y]=='O') {
                    ans = cur.step;
                    break;
            }
            for(int i =0;i<4;i++){
           
//                if(cur.prevDir != -1){
//                    //반대방향은 안해요.
//                    if(cur.prevDir == i) continue;
//                    if(((cur.prevDir+2)%4)==i) continue;
//                }
                Point nRed = new Point(cur.red.x,cur.red.y);
                Point nBlue = new Point(cur.blue.x,cur.blue.y);
                //getPriority를 통해 누가 먼저 움직일지 정해준다.
                if(getPriority(cur.red,cur.blue, i)){
                    move(nRed, nBlue, i);
                    move(nBlue,nRed,i);
                }else{
                    move(nBlue,nRed,i);
                    move(nRed,nBlue,i);
                }
                //상태공간의 이해
                if(!visited[nRed.x][nRed.y][nBlue.x][nBlue.y]){
                    visited[nRed.x][nRed.y][nBlue.x][nBlue.y] = true;
                    queue.add(new Status(nRed, nBlue, cur.step + 1));
                }
            }
        }
        System.out.println(ans);
    }
    public static boolean getPriority(Point red, Point blue, int dir){
        if(dir ==0) return red.x<=blue.x;
        else if(dir ==1) return red.y>=blue.y;
        else if(dir ==2) return red.x>=blue.x;
        else return red.y<=blue.y;
    }
    public static void move(Point movingBall, Point anotherBall, int d){
        int nx = movingBall.x;
        int ny = movingBall.y;
        while(map[nx][ny]!='#'){
            if(map[anotherBall.x][anotherBall.y] != 'O'){
                if(nx==anotherBall.x && ny == anotherBall.y)
                    break;
            }
            movingBall.x = nx;
            movingBall.y = ny;
            if(map[nx][ny] == 'O') break;
            nx += dir[d][0];
            ny += dir[d][1];
        }
    }
}

 

방문여부 체크하기

항상 문제를 풀면서 데이터들이 어디서 돌아다녀야하는지에 대한 '상태공간'에 대한 이해가 필요하다.

어떤 상태를 어떻게 정의할 수 있을지 우선적으로 생각하는 것이 좋다.

1step으로 가든, 2step으로 가든 도착한 위치가 같다면 다시 체크해주지 않아도 이미 체크를 한 것과 마찬가지이다.

dp처럼 생각해도 무방하다. 

상태공간의 이해는 '백준 Q2251 물통 '문제를 풀면서 느낌이 확 왔던것 같다.

3. 더 생각해보기와 얻어가는 점

처음에 중복체크를 따로 할 생각을 하지 않았다.

왜냐하면 직관적으로 보았을 때, 왔던 방향으로 더 갈 필요도 없고, 왔던 방향 반대로 다시 갈 필요도 없다고 생각했다.

그러다가 어떤 case에서 확인해보았을 때 구슬이 왔던방향으로는 못가고 위아래는 막혀있어서 더이상 움직이지 못하는 상황에서 count를 10을 채우는 걸 보고 단순하게 '움직였는데 같으면 안가도 되지'라고 생각하고 조건문을 추가했다.

 

그래서 처음에 답이 나왔을 때는 시간이 148ms가 나왔고 조금 더 줄여보기 위해 생각해보다가 결국, '움직였는데 같으면 안가도 된다' 라는 말이 '어떻게 해서 왔는데 같은 position이면 또 움직일 필요가 없지'라는 생각을 하게 되었다.

위치 하나만으로 중복체크가 가능하고 pruning이 되는 것을 position과 방향 그리고 step까지 생각하면서 할 필요가 없었다.  이 부분을 고쳐주니 조금 더 빨라진 결과를 받을 수 있었다.