BOJ_13459 : 구슬 탈출

👉 문제링크

13459번: 구슬 탈출

---

< 예제 생략 >

---

🔸 문제 분석 🔸

• N x M 보드판에 모서리는 막혀있고, 빨간 공 : R, 파란 공 : B, 구멍 : O 가 주어진다.
  • 보드판을 기울이면 두 공이 움직일 수 있는 공간 끝까지 한쪽으로 이동한다.
  • 빨간 공 만 구멍으로 뺄 수 있으면 1, 없으면 0 을 출력한다.
• 보드판을 기울이는 4가지 선택에 따른 결과를 확인해야 하므로 BFS를 사용한다.
• 공의 굴러감, 게임 종료 확인을 시뮬레이션한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static char[][] map;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        // Input
        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];
        int[] start = new int[4];
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                char c = s.charAt(j);
                if (c == 'R') {
                    start[0] = i;
                    start[1] = j;
                    map[i][j] = '.';
                } else if (c == 'B') {
                    start[2] = i;
                    start[3] = j;
                    map[i][j] = '.';
                } else {
                    map[i][j] = c;
                }
            }
        }

        // BFS + Output
        System.out.println(bfs(start));
    }

    private static int bfs(int[] start) {
        Queue<int[]> que = new ArrayDeque<>();
        que.add(start);
        int cnt = 1;
        while (!que.isEmpty() && cnt <= 10) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                int[] points = que.poll();
                for (int j = 0; j < 4; j++) {
                    int[] result = new int[4];      // 굴렸을때 공 위치
                    int ret = go(j, points, result);   // 공 굴려보기
                    if (ret == 1) return 1;         // 정답 찾음
                    else if (ret == 0) {            // 진행은 가능
                        que.add(result);
                    }
                }
            }
            cnt++;
        }
        return 0;
    }

    private static int go(int d, int[] points, int[] result) {
        boolean red = false, blue = false;
        int rx = points[0];
        int ry = points[1];
        int bx = points[2];
        int by = points[3];

//        System.out.println(rx + " " + ry + " " + bx + " " + by + " " + d);

        // 빨간 공 굴리기
        while (map[rx + dx[d]][ry + dy[d]] != '#') {
            rx += dx[d];
            ry += dy[d];
            if (map[rx][ry] == 'O') {
                red = true;
                break;
            }
//            System.out.println(rx + " " + ry);
        }

        // 파란 공 굴리기
        while (map[bx + dx[d]][by + dy[d]] != '#') {
            bx += dx[d];
            by += dy[d];
            if (map[bx][by] == 'O') {
                blue = true;
                break;
            }
        }

        if (blue) return 2;         // 파란공 들어가버림 (진행불가)
        else if (red) return 1;     // 빨간 공만 들어감 (성공)
        else {                      // 둘 다 안들어감 (계속 진행)
            if (rx == bx && ry == by) {  // 두 공이 겹침
                if (first(d, points)) {      // 빨간 공이 빠름
                    bx += dx[(d + 2) % 4];
                    by += dy[(d + 2) % 4];
                } else {                    // 파란 공이 빠름
                    rx += dx[(d + 2) % 4];
                    ry += dy[(d + 2) % 4];
                }
            }
            result[0] = rx;
            result[1] = ry;
            result[2] = bx;
            result[3] = by;
            return 0;
        }
    }

    private static boolean first(int d, int[] points) {
        if (d == 0) {
            return points[0] < points[2];
        } else if (d == 1) {
            return points[1] > points[3];
        } else if (d == 2) {
            return points[0] > points[2];
        } else {
            return points[1] < points[3];
        }
    }
}

🔸 코드 해석 🔸

• 보드판 정보를 입력 받을 때 공들의 좌표를 start 배열에 저장하고 그 자리는 빈 공간 '.'으로 저장한다.
• BFS를 돌려 빨간공만 빠져나올 수 있는지 판단한다.
  • 격자판을 기울이는 방향에 따라 달리지는 경우의 수를 큐에 담아가며 계산한다.
  • 격자판을 기울인 후 공의 위치나 결과는 go 메서드에서 구한다.
    • while문으로 두 공을 끝까지 돌려보고 파란공이 들어갔으면 진행불가, 빨간공만 들어갔으면 성공으로 판단한다.
    • 만약 두 공이 겹쳤으면 방향에 따라 먼저 이동한 공을 first메서드로 찾아 뒤늦게 움직인 공을 한 칸 뒤로 돌린다.
    • 진행불가는 2, 성공은 1, 계속 진행해 봐야 되면 0을 리턴한다.
  • 성공하면 bfs 메서드를 종료하고, 계속 진행해야 되면 큐에 좌표를 넣는다.
• 결과를 출력한다.

---

🔸 end 🔸

• 처음엔 dfs로 접근했다가 코드가 너무 복잡해져서 bfs로 다시 한 번 풀었다.
  • 그래도 틀리는 부분이 있어서 질문 게시판을 참고했다.
  • 구슬 탈출 2의 테스트 케이스를 돌려보고 틀린 점을 발견했는데, bfs의 while문을 들어가기 전 cnt의 초기값을 1이 아닌 0으로 줘서 오답이 나왔었다.
    • cnt는 보드판을 기울인 횟수이다.