문제
https://www.acmicpc.net/problem/15653
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
출력
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 어떻게 움직여도 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
풀이
접근방법
시간제한 2초, 메모리 512MB이다.
3 ≤ N, M ≤ 10
BFS를 활용하여 풀 수 있는 문제이다.
단순 BFS를 넘어 조금 더 복잡한 BFS로 가면
순서가 정해진 탐색을 하거나, 여러개의 Queue를 사용하거나 하는 등의 작업들을 요구한다. 이 문제도 그런 유형들 중 하나의 문제이다.
총 4개의 구슬 탈출 시리즈가 있다.
그중 4번 문제가 개인적으로 가장 어려운 문제였다.
4번 문제를 해결했다면, 나머지 3문제도 금방 해결할 수 있을 것이다.
https://www.acmicpc.net/problemset?search=%EA%B5%AC%EC%8A%AC+%ED%83%88%EC%B6%9C
빨간 구슬과 파란 구슬이 항상 1개 있다는 사실과 어떻게 해도 불가능한 경우가 나온다는 것을 문제를 보고 반드시 파악해야 한다.
하나의 큐를 이용해서 문제를 풀어보자.
하나의 큐로 가능하다는것을 우선 이해해야 한다.
1. 어느 방향으로 기울여도 항상 2개의 구슬이 이동한다.
(벽에 막혀서 0칸 이동하는것도 포함)
2. BFS를 사용하며, 빨간공과 파란공이 같은 Depth에서 움직인다.즉, 일반적인 BFS의 경우, 하나를 Queue에서 꺼내서 특정 작업을 수행한 뒤 변경된 위치에서 다시 BFS 탐색을 시작한다.
이 문제에서는 빨간 구슬과 파란 구슬을 하나의 세트로 인식하고 접근한다.
하지만 위 과정에서 생기는 문제점이 하나 있다.
// 예시1. 잘못된 경우
###### ######
#RB..# => #R..B#
###### ######Queue에서 빨간 구슬과 파란 구슬을 하나의 세트로 꺼내서 하나씩 이동시킨다.
코드는 순차적으로 실행되기 때문에 빨간 구슬의 경우, 파란 구슬에 막혀서 오른쪽으로 이동할 수 없다.
하지만 파란 구슬은 이동할 수 있다.
// 예시2. 정상적인 경우
###### ######
#RB..# => #..RB#
###### ######예시2와 같이 정상적으로 이동하기 위해서 어떻게 해야할까?
빨간 구슬과 파란구슬을 다루는 배열을 따로 만들어야할까?
정답은 파란 구슬이 움직인뒤, 빨간 구슬을 다시 한 번 더 이동시키면 된다.
정리하자면 아래의 흐름과 같다.
1. 빨간 구슬과 파란 구슬을 세트로 꺼낸다.
a. Queue에서 첫 번째 꺼낸 것은 빨간 구슬 두 번째로 꺼낸것은 파란 구슬
2. 어느 방향으로 먼저 기울여 볼지 정한다.
3. 구슬을 이동시켜본다.
a. 먼저 꺼낸 구슬을 이동시킨다.
b. 이후에 꺼낸 구슬을 이동시킨다.
c. 먼저 꺼낸 구슬을 한 번 더 이동시켜본다.
( 3a 과정에서 다른 구슬에 막혀있었으나, 3b 과정에 의해 움직일 수 있는 가능성이 생겼기 때문)
4. 이미 가본 곳(빨간 구슬과 파란 구슬의 좌표쌍)은 가지 않는다.
5. 구슬이 빠졌다면 각각의 경우에 대해 처리한다.
a. 빨간 구슬만 빠졌는가?
b. 파란 구슬만 빠졌는가?
c. 두 개의 구슬이 동시에 빠졌는가?- 4번 과정이 필요한 이유.
아래와 같은 입력이 있다고 가정하자.
오른쪽-왼쪽 순서로 기울였을 때, 무한 루프에 빠진다.
#######
#R..#B#
##O####
#######
구슬 탈출 시리즈의 나머지 문제들의 경우, 더 고려해야할 조건이 적거나
추가적으로 출력을 요구한다.
문제를 제대로 이해했다면, 기존 코드를 일부 변형만으로 모두 해결 할 수 있다. 이해를 하였는지 긴가민가 하다면, 꼭 나머지 문제도 풀어보자.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
static StringBuilder sb;
static int N, M;
static char[][] map;
static boolean[][][][] visit;
static class Point {
int x;
int y;
Point(int a, int b) {
x = a;
y = b;
}
}
static Point hole, red, blue;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
String[] splitedLine = in.readLine().split(" ");
N = stoi(splitedLine[0]);
M = stoi(splitedLine[1]);
map = new char[N][M];
visit = new boolean[N][M][N][M];
for (int i = 0; i < N; ++i) {
String str = in.readLine();
for (int j = 0; j < M; ++j) {
map[i][j] = str.charAt(j);
if (map[i][j] == 'R') {
red = new Point(i, j);
map[i][j] = '.';
} else if (map[i][j] == 'B') {
blue = new Point(i, j);
map[i][j] = '.';
} else if (map[i][j] == 'O') {
hole = new Point(i, j);
} else {
}
}
}
Queue<Point> q = new ArrayDeque<>();
q.add(red);
q.add(blue);
visit[red.x][red.y][blue.x][blue.y] = true;
int depth = 1;
while (!q.isEmpty()) {
int size = q.size() / 2;
while (size-- > 0) {
Point curRed = q.poll();
Point curBlue = q.poll();
for (int d = 0; d < 4; ++d) {
Point nextRed = moveBall(curRed, curBlue, d); // red 먼저 움직이기
Point nextBlue = moveBall(curBlue, nextRed, d); // blue 움직이기
if (!isIn(nextRed)) {
nextRed = moveBall(nextRed, nextBlue, d); // blue가 움직여서 red가 더 움직여 질 수 있으므로 한번더
}
// 둘 다 이상 없다면 큐에 추가
if (!isIn(nextRed) && !isIn(nextBlue) && !visit[nextRed.x][nextRed.y][nextBlue.x][nextBlue.y]) {
visit[nextRed.x][nextRed.y][nextBlue.x][nextBlue.y] = true;
q.add(nextRed);
q.add(nextBlue);
continue;
}
// 특정 구슬이 들어갔다면 중단.
boolean flag = false;
if (isIn(nextBlue)) {
flag = true;
// nothing
}
if (isIn(nextRed) && flag == false) {
System.out.println(depth);
return;
}
}
}
depth++;
}
System.out.println(-1);
}
public static boolean isIn(Point p) {
if (p.x == -1 && p.y == -1)
return true;
return false;
}
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
private static Point moveBall(Point p, Point another, int d) {
int curX = p.x;
int curY = p.y;
int nextX = p.x;
int nextY = p.y;
while (true) {
nextX = nextX + dx[d];
nextY = nextY + dy[d];
if (map[nextX][nextY] == '#' || (nextX == another.x && nextY == another.y)) {
return new Point(curX, curY);
} else if (map[nextX][nextY] == '.') {
curX = nextX;
curY = nextY;
} else {
return new Point(-1, -1);
}
}
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}