[BOJ/C++] 13460번 구슬 탈출 2
문제
문제 해석
10 * 10 크기의 보드에 구멍 하나와 빨간 구슬, 파란 구슬이 있을 때, 빨간 구슬만 구멍에 통과하도록 보드를 기울여야 한다.
첫 아이디어
빨간 구슬을 기준으로 상하좌우 방향을 확인한다. 최소 횟수를 출력해야 하고, 두 구슬이 함께 이동하는 동시성이 있으므로, BFS 알고리즘을 사용한다.
이동할 수 있다면, 벽을 만나거나 구멍을 만나기 전까지 빨간 구슬 이동/파란 구슬 이동을 반복한다. 이때 빨간 구슬, 파란 구슬 각각에 대해 visited 배열을 사용한다.
✅ 이렇게 구현하니 빨간 구슬, 파란 구슬 각각에 대해 visited 배열을 사용하는 점, 빨간 구슬과 파란 구슬 이동 시 벽/구멍/다른 구슬 존재 여부 확인이 까다로웠다.
혼자서 생각하고 구현하기 어려워서, 많은 블로그와 유튜브를 참고했다. 가장 도움이 된 유튜브와 설명 링크를 첨부한다!
참고한 아이디어
다른 BFS 알고리즘 문제를 풀 때 움직이는 대상이 하나인 경우가 많았다. 하지만 이 문제에서는 움직임 한 번에 두 개의 위치가 변하고, 위치에 따른 출력 조건이 까다로웠다.
✅ 설명 링크에 따르면, 움직임 한 번에 대해서 빨간 구슬, 파란 구슬을 동시에 관리한다! 움직임마다의 상태 자체를 queue를 이용해 기록한다!! 아래 사진은 설명 링크에 나온 한 페이지를 가져온 것이다.
시간 복잡도
보드의 크기가 10*10으로 작다. 최대 움직임이 10번이기 때문에 4^10, 한 번의 움직임에 가로로 쭉 이동하거나 세로로 쭉 이동하는 10번만 확인하면 되어서 Worsest 시간 복잡도가 10 * 4^10이다. 2^10 = 1024를 10^3으로 근사하면 10 \* 10^6 만에 풀리므로 시간 초과가 발생하지 않는다.
하지만 움직임의 방향을 BFS 알고리즘으로 판단한다면, 상하좌우 중에서 이전에 이동해온 방향, 바로 직전에 이동해온 방향을 제외할 수 있다. 첫 움직임만 네 방향을 탐색하고, 그 이후의 움직임에 대해서는 두 방향만 탐색할 수 있기 때문에 훨씬 적은 시간복잡도를 갖도록 구현할 수 있다. (이 역시도 설명 링크에 나와 있다.)
구현 방향
변수 선언
✅ 움직임마다의 상태 자체를 INFO 구조체로 관리한다. BFS 알고리즘을 사용할 것이기 때문에, queue를 선언한다.
✅ 사차원 배열을 이용해서, 하나의 상태에 대해 방문 체크를 할 수 있다. (처음 만난 사차원 배열 문제라서 익숙하진 않지만, 추후 같은 사용처가 나온다면 링크를 걸도록 하겠다!)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <queue>
using namespace std;
int N, M; // height, width
typedef struct INFO {
int ry, rx, by, bx, count;
};
queue<INFO> q;
INFO start;
char board[10][10];
int visited[10][10][10][10] = { 0, };
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};
int answer = -1;
int main()
// input
✅ 다른 사람들의 문제 풀이를 보다가 깨달은 것이 있다. 지금까지 BFS 문제를 풀 때 bfs() 콜을 하기 전에 q에 push하고 visited를 체크했는데, 모듈화의 관점에서 보면 bfs() 안에서 체크하는 것이 더 좋은 코드라고 생각한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int main() {
// input
cin >> N >> M;
for (int i = 0; i < N; i++) {
string input;
cin >> input;
for (int j = 0; j < M; j++) {
board[i][j] = input[j];
// start INFO initialize
if (board[i][j] == 'R') {
start.ry = i;
start.rx = j;
}
if (board[i][j] == 'B') {
start.by = i;
start.bx = j;
}
}
}
// start INFO initialize
start.count = 0;
cout << bfs();
}
int bfs()
✅ 모듈화의 관점에서, push와 visited 체크를 int bfs() 안에 작성했다. 큰 구조는 일반적인 BFS 문제와 동일하다.
10번 이상 탐색하는 실패 조건, 빨간 구슬은 구멍에 들어가고 파란 구슬은 구멍에 들어가지 않는 성공 조건을 작성했다.
// find next condition
특정 방향에 대해, 빨간 구슬을 이동시키고 파란 구슬을 이동시킨다. board에서 벽이거나 구멍이 아니면 구슬이 이동한다. 만약 위치가 벽이라면, 이동해온 방향의 반대 방향으로 한 칸 이동해서 벽에 구슬이 있을 수 없다는 조건을 만족시킨다.
// RED, BLUE positon check
만약 빨간 구슬과 파란 구슬을 이동시켰는데, 위치가 같다면, 더 뒤에서 현재 위치까지 이동한 구슬을 한 칸 반대로 이동시켜 두 구슬이 한 칸에 있을 수 없다는 조건을 만족시킨다.
✅ 여기까지 한 번의 움직임이 끝났으므로 다음 움직임을 위해 다음 위치를 기록한다. 방문하지 않았다면(이 상태를 확인한 적이 없다면) 방문 체크를 하고 빨간 구슬, 파란 구슬의 위치를 기록한다. 움직임도 1 증가시키고 q에 push한다. 만약 방문했다면 (이 상태를 확인한 적이 있다면) 다음 방향에 대해 구슬을 움직인다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
int bfs() {
q.push(start);
visited[start.ry][start.rx][start.by][start.bx] = 1;
while (!q.empty()) {
INFO cur = q.front();
q.pop();
// fail condition
if (cur.count > 10) break;
// success condition
if (board[cur.ry][cur.rx] == 'O' && board[cur.by][cur.bx] != 'O') {
answer = cur.count;
break;
}
// find next position
for (int d = 0; d < 4; d++) {
int next_ry = cur.ry;
int next_rx = cur.rx;
int next_by = cur.by;
int next_bx = cur.bx;
// RED moving
while (1) {
// until wall or hole
if (board[next_ry][next_rx] != '#' && board[next_ry][next_rx] != 'O') {
next_ry += dy[d], next_rx += dx[d];
}
else {
if (board[next_ry][next_rx] == '#') {
next_ry -= dy[d], next_rx -= dx[d];
}
break;
}
}
// BLUE moving
while (1) {
// until wall or hole
if (board[next_by][next_bx] != '#' && board[next_by][next_bx] != 'O') {
next_by += dy[d], next_bx += dx[d];
}
else {
if (board[next_by][next_bx] == '#') {
next_by -= dy[d], next_bx -= dx[d];
}
break;
}
}
// RED, BLUE positon check
if (next_rx == next_bx && next_ry == next_by) {
if (board[next_ry][next_rx] != 'O') {
int red_dist = abs(next_ry - cur.ry) + abs(next_rx - cur.rx);
int blue_dist = abs(next_by - cur.by) + abs(next_bx - cur.bx);
if (red_dist > blue_dist) {
next_ry -= dy[d];
next_rx -= dx[d];
}
else {
next_by -= dy[d];
next_bx -= dx[d];
}
}
}
if (visited[next_ry][next_rx][next_by][next_bx] == 0) {
visited[next_ry][next_rx][next_by][next_bx] = 1;
INFO next;
next.ry = next_ry;
next.rx = next_rx;
next.by = next_by;
next.bx = next_bx;
next.count = cur.count + 1;
q.push(next);
}
}
}
return answer;
}