백준 13460번 <구슬 탈출 2>

백준 알고리즘 13460번

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

13460번: 구슬 탈출 2

---

13460번

구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

 

입력으로 첫 줄에 직사각형 보드의 세로 길이 N과 가로 길이 M이 들어온다.

그 다음 N개의 줄에 걸쳐 보드의 상태가 주어진다.

 

출력으로 빨간 구슬이 탈출하기 위해 움직여야 하는 최소 횟수를 출력하면 된다. 이때, 빨간 구슬이 10번 안에 탈출하지 못하면 -1을 출력하면 된다.

---

문제 해결

13459번 구슬 탈출 문제를 풀었는데 다른 사람들에 비해 시간이 오래 걸리고 메모리를 많이 사용했길래 세트 문제인 이 문제를 다른 방식으로 풀어보고 싶어서 풀게 되었다.

 

13459번 문제와 비슷하게 풀었지만 다른 점은 재귀 함수를 이용해 풀었다는 점이다. (13459번 문제는 중복순열을 이용해 풀었다.) 

 

빨간 구슬과 파란 구슬 중에서 어떤 구슬을 먼저 움직일지 결정하는 first 함수를 작성했다.

first 함수를 작성할 때는 아래와 같은 규칙을 이용했다.

 

그 다음에 구슬을 움직이는 함수를 작성했다.

구슬을 한 방향으로 움직이면서 움직임을 멈추는 경우는 3가지가 있다.

1. 범위를 벗어났거나 벽을 만난 경우
2. 탈출구를 만난 경우
3. 다른 구슬을 만난 경우

1번의 경우와 3번의 경우를 한꺼번에 쓸 수도 있었지만, 만약 빨간 구슬을 먼저 움직이고 파란 구슬을 움직인다고 할 때, 빨간 구슬이 탈출구를 만나서 위치가 바뀌게 되고, 파란 구슬도 탈출구를 만났지만 3번의 경우로 빠져나가버려서 탈출구를 만나지 못했다고 기록되기 때문에 나눠서 작성하였다.

 

실질적인 로직을 진행하는 recursion 함수는 다음과 같은 로직을 따른다.

1. 이미 10번 움직였다면 더 이상 재귀 호출을 진행하지 않는다.
2. 먼저 움직여야 할 구슬의 인덱스를 구한 뒤 순서대로 구슬을 움직인다.
3. 만약 파란 구슬이 탈출했다면 해당 게임은 실패했으므로 더 이상 재귀 호출을 진행하지 않는다.
4. 만약 빨간 구슬이 탈출했다면 (위에서 파란 구슬이 탈출한 경우는 걸러졌기 때문에 빨간 구슬만 탈출한 경우이다.) 해당 게임은 성공했으므로 정답을 업데이트하고 더 이상 재귀 호출을 진행하지 않는다.
5. 다음 움직임을 위해 recursion 함수를 재귀 호출하는데 이때, 4가지 방향 중 현재 방향을 뺀 3가지 방향으로 움직인다.

---

코드

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

public class BOJ_13460 {
    static class Point{
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N, M, ANS;
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};
    static char[][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        N = Integer.parseInt(inArr[0]);     // N : 세로길이
        M = Integer.parseInt(inArr[1]);     // M : 가로길이
        board = new char[N][M];
        Point[] beads = new Point[2];
        for (int i = 0; i < N; i++) {
            board[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 'R'){
                    beads[0] = new Point(i, j);
                }else if(board[i][j] == 'B'){
                    beads[1] = new Point(i, j);
                }
            }
        }
        // end input

        ANS = Integer.MAX_VALUE;    // ANS : 빨간 구슬이 탈출하는 최소 움직임 횟수
        for (int k = 0; k < 4; k++) {
            // 4가지 방향을 각각 시작으로 하는 recursion 함수 호출
            recursion(k, 0, deepcopy(beads));
        }
        // 한번도 update 되지 않았다면 10번 안에 빨간 구슬이 탈출하지 못한 것
        System.out.println(ANS == Integer.MAX_VALUE ? -1 : ANS);

    }

    /**
     *
     * @param k     : 이동하는 방향
     * @param cnt   : 현재 이동 횟수
     * @param pnts  : pnts[0] - 빨간 구슬 위치, pnts[1] - 파란 구슬 위치
     */
    static void recursion(int k, int cnt, Point[] pnts){
        if (cnt == 10) return;      // 10번 이상 할 필요 없음
        int f = first(k, pnts);     // f : 먼저 움직여야 하는 구슬 인덱스
        int s = f == 0 ? 1 : 0;     // s : 그 다음에 움직여야 하는 구슬 인덱스
        // 구슬 움직이기
        pnts = UDLR(k, f, pnts);
        pnts = UDLR(k, s, pnts);

        // 파란 구슬이 빠져나옴 -> 더 이상 재귀 진행 할 필요 없음
        if (board[pnts[1].x][pnts[1].y] == 'O') return;
        // 빨간 구슬이 빠져나옴 -> 더 이상 재귀 진행 할 필요 없음 + 정답 업데이트
        if (board[pnts[0].x][pnts[0].y] == 'O') {
            ANS = Math.min(ANS, cnt+1);
            return;
        }
        // 현재 진행한 방향 말고 다른 방향들로 recursion 함수 재귀 호출
        for (int p = 0; p < 4; p++) {
            if (k == p) continue;
            recursion(p, cnt+1, deepcopy(pnts));
        }

    }

    /**
     *
     * @param k     : 이동하는 방향
     * @param idx   : 움직일 구슬 인덱스
     * @param pnts  : pnts[0] - 빨간 구슬 위치, pnts[1] - 파란 구슬 위치
     * @return
     */
    static Point[] UDLR(int k, int idx, Point[] pnts) {
        int chk = idx == 0 ? 1 : 0;     // chk : 현재 움직이는 구슬 말고 다른 구슬의 인덱스
        int nx = pnts[idx].x;
        int ny = pnts[idx].y;
        while(true){
            nx += di[k];
            ny += dj[k];
            // 범위를 벗어나거나 벽을 만났다면 그 전 위치를 기록
            if(nx < 0 || ny < 0 || nx >= N || ny >= M || board[nx][ny]=='#'){
                pnts[idx].x = nx - di[k];
                pnts[idx].y = ny - dj[k];
                break;
            }
            // 탈출했다면 해당 위치를 기록
            if (board[nx][ny] == 'O'){
                pnts[idx].x = nx;
                pnts[idx].y = ny;
                break;
            }
            // 다른 구슬을 만났다면 그 전 위치를 기록
            if (nx == pnts[chk].x && ny == pnts[chk].y){
                pnts[idx].x = nx - di[k];
                pnts[idx].y = ny - dj[k];
                break;
            }
        }
        return pnts;
    }

    // 먼저 움직여야 하는 index를 반환
    static int first(int k, Point[] pnts){
        int red = pnts[0].x * di[k] + pnts[0].y * dj[k];
        int blue = pnts[1].x * di[k] + pnts[1].y * dj[k];
        return red > blue ? 0 : 1;
    }

    static Point[] deepcopy(Point[] pnts) {
        Point[] copy = new Point[2];
        copy[0] = new Point(pnts[0].x, pnts[0].y);
        copy[1] = new Point(pnts[1].x, pnts[1].y);
        return copy;
    }
}

---

결과

 

---