🔍 13460 구슬 탈출 2
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
🤔 풀이
(4시간동안 하입보이 반복하면서 문제 푸는 나의 모습..)
- 우선 큰 순서를 다음과 같이 생각했다.
[DFS(backtracking)]
1. promising한지 (두 구슬 중 적어도 하나라도 이동했을 때)
1-1. DFS 이동
[promising]
1. 구슬 두 개를 움직여본다. move_ball
2. 두 구슬의 처음 상태와 마지막 상태를 비교한다.
3-1. 만약 둘 다 처음, 마지막 상태가 똑같다(0, 0)면 non-promising
3-2. 만약 둘 중 하나라도 탈출한 구슬이 있다(-1, X or X, -1)면 non-promising
3-2-1. 실패 (X, -1)
3-2-2. 성공 (-1, 0/1)
3-3. 만약 둘 중 하나라도 움직였다면 promising
[move_ball]
1. 우선 장애물을 만날 때까지 계속 움직여본다. (1)
2. 만약 이동하다가 탈출구를 만나면 그 위치로 고정 후 종료. (-1)
3. 만약 그 장소가 다른 구슬이 있는 위치라면 이전 위치로 이동 후 종료. (1)
4. 끝에서, 해당 구슬이 원래 위치에서 벗어나지 않았으면 (0)- 처음 생각엔 백트래킹을 돌면서, promising한지 검사할 때 구슬이 더 이상 움직이지 않을 때 자연스럽게 종료되니까 문제 없을 줄 알았다. 다만 구슬이 반복해서 움직이며 (온 곳을 다시 되돌아가는 등) 출구를 찾으려고 종료되지 않기 때문에 계속해서 segmentation fault가 발생했다.
- 해당 케이스를 방지하기 위해 visit을 확인하게 만들어야하나... 생각하던중 이미 3시간동안 머리 아파하며 시간을 쓰고 있었기 때문에 검색 찬스를 사용했다. N, M이 10 이하이므로, 구슬이 10번 이동하면 그 이후로는 확인할 필요가 없다는 것이다! (+추가로, 방금 직전에 기울인 방향으로 또 기울이거나, 그 반대 방향으로 기울이는 것은 의미가 없기 때문에 해당 케이스를 확인해주면 불필요한 계산을 줄일 수 있다. 나는 너무 지쳐서 그것까진 포함하지 않았다...
약간 찝찝하지만..) - 단순한 조건만 생각해서 구현하는게 아니라 조금 더 생각해 보아야 하는구나 느꼈던 문제... 최종적으로는 다음과 같은 과정으로 진행된다.
[DFS(backtracking)]
1. 만약 해당 depth가 이미 10을 넘었다면 수행을 그만둔다.
2. 해당 위치에서 구슬들을 상하좌우로 굴려본다.
2-1. 이때, 방향별로 구슬들이 굴러가는 우선순위가 바뀐다. 따라서 이를 계산 후, 각각의 구슬을 굴린다.
2-2. 구슬을 한 방향으로 굴렸을때, 결과가 promising한지 확인한다.
(promising : 두 구슬 중 적어도 하나가 움직였고, 두 구슬 모두 탈출하지 않았을 때)
2-2-1. 만약 빨간색 구슬만 탈출했다면 몇 번의 수행이 있었는지 계산한다.
2-2-2. promising하다면, 다음 DFS.
[move_ball]
1. 구슬을 장애물을 만나기전까지 계속 굴려본다.
1-1. 만약 구슬이 탈출구를 만났다면, 탈출구를 위치로 삼아 이동을 종료한다 (return -1)
1-2. 만약 구슬이 다른 구슬과 만났다면, 해당 구슬을 만나기 전의 위치로 이동하고 이동을 종료한다.
1-2-1. 만약 그 위치가 처음 있던 위치와 동일하다면 (return 0)
1-2-2. 동일하지 않다면 (return 1)
2. 구슬이 장애물을 만났다면, 장애물을 만나기 전의 위치로 이동하고 이동을 종료한다.
2-1. 만약 그 위치가 처음 있던 위치와 동일하다면 (return 0)
2-2. 동일하지 않다면 (return 1)
=> 0 : 구슬이 움직이지 않았을 때, 1 : 구슬이 움직였고, 탈출구를 만나지 않았을 때, -1 : 구슬이 탈출구를 만났을 때.📝 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
char board[10][10];
int N, M;
int step, ans = 987654321;
pair<int, int> ball[2];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int move_ball(int ball_num, int dir) {
int nx = ball[ball_num].first; int ny = ball[ball_num].second;
while (board[nx + dx[dir]][ny + dy[dir]] != '#') {
nx = nx + dx[dir];
ny = ny + dy[dir];
if (board[nx][ny] == 'O') { // 탈출구
ball[ball_num].first = nx;
ball[ball_num].second = ny;
return -1;
}
if (nx == ball[(ball_num+1)%2].first && ny == ball[(ball_num+1)%2].second) { // 다른 구슬과 만났을 때
if (ball[ball_num].first == nx - dx[dir] && ball[ball_num].second == ny - dy[dir]) { // 해당 구슬이 한 번도 이동하지 않았을 때
return 0;
}
ball[ball_num].first = nx - dx[dir];
ball[ball_num].second = ny - dy[dir];
return 1;
}
}
if (ball[ball_num].first == nx && ball[ball_num].second == ny) { // 해당 구슬이 한 번도 이동하지 않았을 때
return 0;
}
ball[ball_num].first = nx;
ball[ball_num].second = ny;
return 1;
}
int get_order(int dir) { // 우선순위를 결정해준다.
int rx = ball[0].first, ry = ball[0].second, bx = ball[1].first, by = ball[1].second;
if (dx[dir]!=0) { // x가 움직임, y가 같은곳에 있는지 비교.
if (ry == by) {
// 만약 dx[dir] = 1이면, x가 큰것이 오더가 높음. eg) 1 2 -> 2... 1 < 2
// -1이면, x가 작은것이 오더가 높음. eg) 1 2 -> 1... -1 > -2
return dx[dir]*rx < dx[dir]*bx;
}
return 0;
}
else { // y가 움직임, x가 같은곳에 있는지 비교.
if (rx == bx) {
return dy[dir]*ry < dy[dir]*by;
}
return 0;
}
}
void dfs(int step) {
if (step > 10) return ;
int red_ball_x = ball[0].first;
int red_ball_y = ball[0].second;
int blue_ball_x = ball[1].first;
int blue_ball_y = ball[1].second;
for (int dir = 0; dir < 4; dir++) {
ball[0].first = red_ball_x;
ball[0].second = red_ball_y;
ball[1].first = blue_ball_x;
ball[1].second = blue_ball_y;
// 볼을 움직이고,
int order = get_order(dir);
int result[2];
result[order] = move_ball(order, dir);
result[(order+1)%2] = move_ball((order+1)%2, dir);
// 결과 확인.
if (result[0] != 0 || result[1] != 0) { // 두 구슬 중 하나라도 움직였다면
if ((result[0] == -1) || (result[1] == -1)) {
if (result[1] != -1) {
ans = min(ans, step);
}
}
else dfs(step+1);
}
}
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> board[i][j];
if (board[i][j] == 'R') {
ball[0] = make_pair(i, j);
board[i][j] = '.';
}
else if (board[i][j] == 'B') {
ball[1] = make_pair(i, j);
board[i][j] = '.';
}
}
}
dfs(1);
if (ans == 987654321) cout << -1;
else cout << ans;
return 0;
}