[백준 - G1] 13460. 구슬 탈출2

문제

이 문제는 격자판 위에서 빨간 구슬 (R) 과 파란 구슬 (B) 을 동시에 움직이는 퍼즐이다. 한 번 움직일 때마다 두 구슬은 같은 방향으로 이동하며, 다음과 같은 규칙을 따른다.

• 선택한 방향으로 벽(#)을 만날 때까지 계속 이동
• 구멍(O)에 빠지면 해당 공은 제거
• 빨간 구슬 만 구멍에 빠지면 성공
• 파란 구슬 이 빠지면 무조건 실패
• 이동 횟수는 최대 10번

목표는 10번 이내에 빨간 구슬만 구멍에 넣을 수 있는지를 판단하는 것이다.

 

풀이

[-1을 출력해야하는 조건]

1. 파란 구슬이 먼저 혹은 동시에 구멍에 빠질 때

2. 10번이 넘어도 빨간 구슬을 못빼낼때

두 공 위치를 방문 처리하기위해 4차원 배열인 visited를 활용한다. 또한 queue에는 굴린 횟수인 depth를 넣어 함께 관리한다.

 

[풀이 과정]

1. 빨간 구슬과 파란 구슬의 위치로 bfs 함수를 실행한다.

2. 한 방향을 선택하면 벽을 만날 때 까지 계속 이동하다, 빨간구슬이 구멍(O) 을 만나면 종료한다.

3. 만약 두 공이 같은 위치에 있다면, 더 많이 이동한 구슬이 한칸 뒤로 이동한다.

ex) R . . . B => . . . R B 가 되어야 한다

주의: 처음에는 파란 구슬이 구멍에 빠지면 return으로 종료하였는데 아래의 경우는 실패하였다.

파란 구슬이 먼저 들어가더라도 빨간 구슬이 먼저 들어가면 성공이어야 하는데, 내 코드에서는 왼쪽으로 먼저 구르다보니 -1이 계속 출력되었다. continue 로 변경해 다른 상황도 고려할 수 있게 변경하였다.

4 6 
###### 
#.ROB# 
#..### 
######
// 정답: 1

 

정답 코드

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

public class Main {

    static int N, M;
    static char[][] map;
    static boolean[][][][] visited;
    static int cnt;

    static class State {
        int rx, ry, bx, by, depth;

        State(int rx, int ry, int bx, int by, int depth) {
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
            this.depth = depth;
        }
    }

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);

        map = new char[N][M];
        int rx = -1, ry = -1;
        int bx = -1, by = -1;
        for (int i = 0; i < N; i++) {
            split = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                map[i][j] = split[j].charAt(0);
                if (map[i][j] == 'R') {
                    rx = i;
                    ry = j;
                } else if (map[i][j] == 'B') {
                    bx = i;
                    by = j;
                }
            }
        }

        visited = new boolean[N][M][N][M];
        cnt = 0;
        bfs(rx, ry, bx, by);
    }

    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };

    static int[] move(int x, int y, int dir) {
        int cnt = 0;
        while (true) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (map[nx][ny] == '#')
                break;
            x = nx;
            y = ny;
            cnt++;
            if (map[x][y] == 'O')
                break;
        }

        return new int[] { x, y, cnt };
    }

    static void bfs(int x, int y, int bx, int by) {

        visited[x][y][bx][by] = true;
        Queue<State> queue = new ArrayDeque<State>();
        queue.offer(new State(x, y, bx, by, 0));

        while (!queue.isEmpty()) {

            State curr = queue.poll();

            if (curr.depth >= 10) {
                System.out.println("-1");
                return;
            }

            for (int i = 0; i < 4; i++) {
                int[] r = move(curr.rx, curr.ry, i);
                int[] b = move(curr.bx, curr.by, i);

                // 파란공이 빠질 경우
                if (map[b[0]][b[1]] == 'O') {
                    continue;
                }
                // 빨간 공이 빠질 경우
                if (map[r[0]][r[1]] == 'O') {
                    System.out.println(curr.depth + 1);
                    return;
                }

                if (r[0] == b[0] && r[1] == b[1]) {
                    if (r[2] > b[2]) { // 빨간공이 왼쪽에 잇으므로 | 빨 | 파 | 이렇게 위치
                        r[0] -= dx[i];
                        r[1] -= dy[i];
                    } else {
                        b[0] -= dx[i];
                        b[1] -= dy[i];
                    }
                }

                if (!visited[r[0]][r[1]][b[0]][b[1]]) {
                    visited[r[0]][r[1]][b[0]][b[1]] = true;
                    queue.offer(new State(r[0], r[1], b[0], b[1], curr.depth + 1));
                }

            }

        }
        System.out.println("-1");
    }
}

 

문제 링크

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