BOJ(백준 온라인 저지) 13460번 with 자바[JAVA]

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

 

어떤 상태에서 나아갈 수 있는 상태가 여럿이 있고, 이를 모두 탐색을 해야하는 경우는

(* 반드시 그래프가 아니더라도)

너비 우선 탐색으로 풀 수 있다.

(* 아니면 A* 알고리즘도 생각해볼 수 있다.)

 

시간복잡도와 공간복잡도

 

너비 우산 탐색을 사용할 때는 시간복잡도와 공간복잡도가 중요하다.

 

최대 10번의 탐색이 이루어져야 하고,

현재 상태에 대해서 최대 두 방향의 가능성이 존재하기 때문에

(* 이전에 선택했던 방향과 그 반대 방향은 제외한다. 예를 들어 왼쪽으로 기울였었는데 다시 왼쪽으로 기울이거나 오른쪽으로 기울이는건 의미없는 반복이다.)

최대 4(* 처음은 네 방향 모두 가능하기 때문에) * 2 * 2 * 2 * ... * 2 ≒ 2^11 = 2048 정도로 생각해볼 수 있다.

 

한 번의 탐색에서 소모되는 시간복잡도가 O(N^4) 이상이어도 가능하다.(* N = 10, 행의 최대 길이)

 

너비 우선 탐색에서 사용되는 Queue안에는 현재 상태가 저장이 되어야한다.

만약 Queue안에 최대 10x10 에 해당하는 행렬 자체를 저장한다면,

 

(* 행렬이 int 타입 2차원 배열이라고 할때)

4byte(* int타입) * 100(* 최대 10x10 행렬) * 1024(* queue안에 저장될 수 있는 상태의 최대 개수) = 409,600 으로 40KB 를 넘지 않는다.

 

따라서 시간복잡도와 공간복잡도 모두 너비 우선 탐색을 사용해도 상관없다.

 

기울임에 따른 구슬들의 움직임

 

구슬이 있고 기울인다면, 기울이는 방향으로 벽이 존재하기 전까지 구슬을 움직여주면 된다.

하지만 구슬들이 부피를 가지고 있고, 구멍을 통해 먼저 구슬이 빠져나가면 그 구슬은 직사각형 보드에서 사라지는 점을 구현해야 한다.

 

구슬들의 부피

 

구슬들이 부피를 가지고 있으니 임의의 방향으로 보드를 기울였을때,

구슬끼리 충돌하는것을 구현해야한다.

 

따라서 구슬이 이동하는 순서가 중요해진다.

예를 들어

 

7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######

 

와 같이 입력이 주어졌을때, 왼쪽 방향으로 기울였다고 가정해보자,

 

R은 (1,1)에 B는 R에 막혀서 (1,2)에 위치할 것이다.

막히려면 R먼저 움직이고 B가 움직여서,

B가 움직일 때, (1,1)자리에는 벽이 존재하는 것처럼 간주되어야한다.

 

즉, 구슬이 움직이는 순서가 중요하다는 의미이다.

왼쪽으로 기울였을때, B가 먼저 움직이고 R이 움직이면,

B는 그 자리 그대로 있을것이고(* R에 시작부터 막혀서)

R은 (1,1)자리에 위치할 것이다.

 

그렇다면 움직이는 순서는 어떻게 정할까?

 

위치이다.

왼쪽으로 움직이는 경우 두 구슬들 중 가장 왼쪽에 있는 구슬먼저 이동시키면 된다.

위로 움직이는 경우에는 두 구슬들 중 가장 위쪽에 있는 구슬먼저 이동시키면 된다.

 

이렇게 해서 구슬의 충돌은 구현 가능해졌다.

 

구멍으로 빠지는 경우

 

구멍으로 빠지는 경우도 간단하다.

예를 들어

 

3 10
##########
#.O....RB#
##########

 

와 같이 입력이 들어왔을때,

왼쪽으로 보드를 기울이면 두 구슬 동시에 빠져나가게 된다.

 

이는 R이 먼저 구멍을 통해 빠지게 되면 그냥 R을 보드 밖으로 내보내버리면 된다.

(* R의 위치를 (-1,-1)등으로 바꿔주면 된다. 이렇게 하면 충돌할 수 없으니...)

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static int R;
    public static int C;
    public static int[][] map;
    public static boolean redOut = false;
    public static boolean blueOut = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // R: # of row, C: # of column
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        // map: 구슬 맵
        map = new int[R][C];
        // (row of R, col of R, row of B, col of B, direct, # of trial)
        int[] RB = new int[6];
        // 초기 상태는 이전에 기울였던 방향이나, 시도의 횟수가 0이기 때문에, 모두 0으로 초기화 해준다.
        RB[4] = 0;
        RB[5] = 0;

        // map 을 초기화 해준다.
        // #, 벽의 경우는 1로 표현해준다.
        // ., 이동할 수 있는 경로의 경우는 0으로 표현해준다.
        // B, 파란 구슬은 그 위치를 RB 에 저장해주고, 그 위치 또한 이동할 수 있는 경로로 표시해둔다.
        // R, 빨간 구슬또한 파란 구슬과 마찬가지로 표시해둔다.
        // O, 구멍은 -1로 표현해준다.
        for(int i=0; i<R; i++){
            String s = br.readLine();
            for(int j=0; j<C; j++){
                if(s.charAt(j) == '#'){
                    map[i][j] = 1;
                }
                else if(s.charAt(j) == '.'){
                    map[i][j] = 0;
                }
                else if(s.charAt(j) == 'B'){
                    // RB[2] 와 RB[3] 은 각각 B의 행과 열의 좌표이다.
                    RB[2] = i;
                    RB[3] = j;
                    map[i][j] = 0;
                }
                else if(s.charAt(j) == 'R'){
                    // RB[0] 과 RB[1] 은 각각 R의 행과 열의 좌표이다.
                    RB[0] = i;
                    RB[1] = j;
                    map[i][j] = 0;
                }
                else{ // O
                    map[i][j] = -1;
                }
            }
        }

        // 너비 우선 탐색을 위한 Queue
        Queue<int[]> queue = new LinkedList<>();
        queue.add(RB);

        // 1: up, 2: down, 3: right, 4: left
        int[] directs = {1, 2, 3, 4};

        // Queue 가 빌때까지 반복, 만약 Queue 가 빈다면 아에 불가능함을 의미
        while(!queue.isEmpty()){
            int[] nowStatus = queue.poll();
            for(int i=0; i<4; i++){
                blueOut = redOut = false;
                // 현재 상태와 움직일 방향을 선택해서 move 메소드를 호출
                int[] nextStatus = move(nowStatus, directs[i]);
                // null 이 리턴되면 그냥 다음 방향을 선택한다.
                if(nextStatus == null)
                    continue;
                // 파란 구슬이 먼저 나오면 그냥 넘어간다.
                if(blueOut){
                    continue;
                }
                // 파란 구슬이 나오지 않고, 빨간구슬이 나왔다는 것은 성공했다는 의미로,
                // 시도횟수를 출력해주고, 프로그램을 종료한다.
                else if(redOut){
                    System.out.println(nextStatus[5]);
                    return;
                }
                // 만약 시도횟수가 10번을 넘어가면 다음 시도를 하지 않고 넘어간다.
                if(nextStatus[5] >= 10){
                    continue;
                }
                // 모든 경우에 해당하지 않다면, 다음 시도를 준비한다.
                queue.add(nextStatus);
            }
        }

        // 그냥 반복문을 나왔다는 것은 아에 불가능함을 의미하므로, -1을 출력해준다.
        System.out.println(-1);
    }

    // 현재 상태와 움직일 방향을 입력받아 다음 상태를 출력해주는 메소드
    private static int[] move(int[] nowStatus, int direct) {
        // 각각의 원소를 구분해서 저장
        int Rrow = nowStatus[0];
        int Rcol = nowStatus[1];
        int Brow = nowStatus[2];
        int Bcol = nowStatus[3];

        // 다음 상태
        int[] returnStatus = new int[6];
        // 다음 상태의 방향은 이동하고자 하는 방향과 같다.
        returnStatus[4] = direct;
        // 시도 횟수는 이전 시도횟수 + 1 로 저장해준다.
        returnStatus[5] = nowStatus[5] + 1;

        // 만약 이동하고픈 방향이 이전에 이동했던 방향과 일치한다면 그냥 넘어간다.
        if(direct == nowStatus[4]){
            return null;
        }
        // 윗 방향으로 움직이고자 한다면,
        else if(direct == 1){
            // 위에 있는 구슬 먼저 움직여야 충돌을 구현할 수 있다.
            if(Rrow >= Brow){
                // B의 row 가 더 작으니 B 먼저 움직인다.
                // B가 앞으로 움직일 방향에 벽이 있다면 반복문을 종료한다.
                while(map[Brow - 1][Bcol] != 1){
                    // 위로 이동
                    Brow--;
                    // 만약 구멍을 통해 나가면
                    if (isOut(Brow, Bcol)) {
                        // blueOut 을 true 로 바꿔줌
                        blueOut = true;
                        // 그리고 B는 map 을 나갔음을 표현하기 위해
                        // B의 row 와 col 값을 0,0 으로 바꿔준다.
                        Brow = 0;
                        Bcol = 0;
                        break;
                    }
                }
                // 그 다음 R 움직임
                while(map[Rrow - 1][Rcol] != 1){
                    if(Rrow - 1 == Brow && Rcol == Bcol) // 쌓이는 경우
                        break;
                    Rrow--;
                    if (isOut(Rrow, Rcol)) {
                        redOut = true;
                        break;
                    }
                }
            }
            else{
                // R 먼저 움직임
                while(map[Rrow - 1][Rcol] != 1){
                    Rrow--;
                    if (isOut(Rrow, Rcol)) {
                        redOut = true;
                        Rrow = 0;
                        Rcol = 0;
                        break;
                    }
                }
                // 그 다음 B 움직임
                while(map[Brow - 1][Bcol] != 1){
                    if(Brow - 1 == Rrow && Rcol == Bcol) // 쌓이는 경우
                        break;
                    Brow--;
                    if (isOut(Brow, Bcol)) {
                        blueOut = true;
                        break;
                    }
                }
            }
        }
        else if(direct == 2) {
            if (Rrow >= Brow) {
                // R 먼저 움직임
                while (map[Rrow + 1][Rcol] != 1) {
                    Rrow++;
                    if (isOut(Rrow, Rcol)) {
                        redOut = true;
                        Rrow = 0;
                        Rcol = 0;
                        break;
                    }
                }
                while (map[Brow + 1][Bcol] != 1) {
                    if (Brow + 1 == Rrow && Rcol == Bcol)
                        break;
                    Brow++;
                    if (isOut(Brow, Bcol)) {
                        blueOut = true;
                        break;
                    }
                }
            } else {
                // B 먼저 움직임
                while (map[Brow + 1][Bcol] != 1) {
                    Brow++;
                    if (isOut(Brow, Bcol)) {
                        blueOut = true;
                        Brow = 0;
                        Bcol = 0;
                        break;
                    }
                }
                // 그 다음 R 움직임
                while (map[Rrow + 1][Rcol] != 1) {
                    if (Rrow + 1 == Brow && Rcol == Bcol) // 쌓이는 경우
                        break;
                    Rrow++;
                    if (isOut(Rrow, Rcol)) {
                        redOut = true;
                        break;
                    }
                }
            }
        }
        else if(direct == 3){
            if(Rcol >= Bcol){
                // R 먼저 움직임
                while(map[Rrow][Rcol + 1] != 1){
                    Rcol++;
                    if (isOut(Rrow, Rcol)) {
                        redOut = true;
                        Rrow = 0;
                        Rcol = 0;
                        break;
                    }
                }
                // 그 다음 B 움직임
                while(map[Brow][Bcol + 1] != 1){
                    if(Bcol + 1 == Rcol && Brow == Rrow) // 쌓이는 경우
                        break;
                    Bcol++;
                    if (isOut(Brow, Bcol)) {
                        blueOut = true;
                        break;
                    }
                }
            }
            else{
                // B 먼저 움직임
                while(map[Brow][Bcol + 1] != 1){
                    Bcol++;
                    if (isOut(Brow, Bcol)) {
                        blueOut = true;
                        Brow = 0;
                        Bcol = 0;
                        break;
                    }
                }
                // 그 다음 R 움직임
                while(map[Rrow][Rcol + 1] != 1){
                    if(Rcol + 1 == Bcol && Rrow == Brow) // 쌓이는 경우
                        break;
                    Rcol++;
                    if (isOut(Rrow, Rcol)) {
                        redOut = true;
                        break;
                    }
                }
            }
        }
        else if(direct == 4) {
            if (Rcol <= Bcol) {
                // R 먼저 움직임
                while (map[Rrow][Rcol - 1] != 1) {
                    Rcol--;
                    if (isOut(Rrow, Rcol)) {
                        redOut = true;
                        Rrow = 0;
                        Rcol = 0;
                        break;
                    }
                }
                while (map[Brow][Bcol - 1] != 1) {
                    if (Bcol - 1 == Rcol && Rrow == Brow)
                        break;
                    Bcol--;
                    if (isOut(Brow, Bcol)) {
                        blueOut = true;
                        break;
                    }
                }
            } else {
                // B 먼저 움직임
                while (map[Brow][Bcol - 1] != 1) {
                    Bcol--;
                    if (isOut(Brow, Bcol)) {
                        blueOut = true;
                        Brow = 0;
                        Bcol = 0;
                        break;
                    }
                }
                // 그 다음 R 움직임
                while (map[Rrow][Rcol - 1] != 1) {
                    if (Rcol - 1 == Bcol && Rrow == Brow) // 쌓이는 경우
                        break;
                    Rcol--;
                    if (isOut(Rrow, Rcol)) {
                        redOut = true;
                        break;
                    }
                }
            }
        }

        returnStatus[0] = Rrow;
        returnStatus[1] = Rcol;
        returnStatus[2] = Brow;
        returnStatus[3] = Bcol;

        return returnStatus;
    }

    private static boolean isOut(int r, int c){
        return map[r][c] == -1;
    }
}

 

배움

 

너비 우선 탐색, A* 알고리즘