문제 : https://www.acmicpc.net/problem/5827
5827번: What's Up With Gravity
Output Details The captain starts at position (4, 2). She flips gravity and falls to position (2, 2) and then moves right twice to arrive at (2, 4). She flips gravity again and falls to position (4, 4) and then moves right once to position (4, 5). Finally
www.acmicpc.net
문제 파악하기
N*M 형태의 2차원 맵에서 C 위치에 있는 캡틴 Bovidian가 목적지 D까지 도달하는데 필요한 최소 중력 변환 횟수를 구하는 문제입니다. Bovidian은 오른쪽과 왼쪽으로 자유롭게 이동할 수 있으며, 중력을 변환하여 움직일 수도 있습니다. 중력 변환 시, 중력 방향으로 벽이 있기 전까지 이동하며, 만약 벽이 없다면 2차원 맵을 벗어나 미션에 실패하게 됩니다. 전형적인 BFS 문제처럼 생긴 이 문제는 캡틴 Bovidian의 위치에서 BFS 탐색을 시작하되, 적절한 최적화를 통해 문제를 해결할 수 있습니다.
문제 해결하기
캡틴 Bovidian은 크게 3가지 방향으로 이동할 수 있습니다. 왼쪽과 오른쪽, 그리고 현재 중력 반대 방향입니다. 왼쪽과 오른쪽으로 이동하는 건 추가 비용이 발생하지 않습니다. 하지만 중력 반대 방향으로 이동하는 데에는 추가 비용이 발생합니다. 그렇기에 우리는 BFS 탐색을 할 때, 추가 비용이 발생하지 않는 왼쪽/오른쪽 이동을 먼저 하고, 추후에 중력의 방향을 바꿔서 이동하는 걸 탐색하면 효율적으로 경우의 수를 판단할 수 있습니다. 보통 이런 연산을 할 때에는 우선순위 큐를 떠올릴 수 있습니다. 하지만 데큐를 사용하면 손쉽게 정렬된 상태를 구현항 수 있습니다.
데큐는 값을 front와 rear 모두 넣을 수 있습니다. 이 점을 활용하여 BFS를 진행하면 효율적으로 탐색을 할 수 있습니다. 왼쪽과 오른쪽으로 이동하는 경우에는 front에 다음 상태를 넣고, 중력을 변환한 경우에는 rear에 다음 상태를 넣으면 항상 데큐에는 정렬된 상태로 상태가 저장됩니다. 물론, 나중에 넣은 값이 먼저 탐색되지만 현재 중력을 변환한 횟수 기준으로 어떤 값을 먼저 탐색하든 상관 없기에 데큐를 활용할 수 있습니다. 이렇게 데큐를 활용하는 기법은 가중치가 0-1인 그래프에서 활용할 수 있으며, 보통 0-1 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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#include <stdio.h>
#include <deque>
#include <utility>
#include <algorithm>
#define NMAX 505
#define INF 0x7FFFFFFF
#define PAIR pair<int, int>
using namespace std;
int N, M, ed;
int pos, f, ret;
char inp[NMAX][NMAX];
deque< PAIR > dq;
int cst[NMAX][NMAX][2];
int curX, curY, curD, nxtCost;
bool safe(int x, int y) {
if(x<0 or y<0 or x>=N or y>=M) return 0;
else return 1;
}
int getPos(int x, int y, int f) {
while(safe(x+f, y) and inp[x+f][y]=='.') x += f;
if(!safe(x+f, y)) return -1; // 외곽으로 벗어난 경우
else if(inp[x+f][y] == '#') return x*M+y;
else return (x+f)*M+y; // 'D'인 경우
}
int main() {
// input
scanf("%d %d", &N, &M);
for(int i=0;i<N;i++) {
scanf("%s", inp[i]);
for(int j=0;j<M;j++) {
if(inp[i][j] == 'C') {
pos = i*M+j;
inp[i][j] = '.';
}
else if(inp[i][j] == 'D') ed = i*M+j;
}
}
// init
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
cst[i][j][0] = cst[i][j][1] = INF;
}
}
// 시작 위치 탐색
pos = getPos(pos/M, pos%M, 1);
ret = INF;
if(pos != -1) {
dq.push_back({pos, 0});
cst[pos/M][pos%M][0] = 0;
// BFS
while(!dq.empty()) {
curX = dq.front().first/M;
curY = dq.front().first%M;
curD = dq.front().second;
dq.pop_front();
if(curX*M + curY == ed) break;
if(curD>0) f = -1;
else f = 1;
// 좌우로 이동
for(int k=-1;k<=1;k+=2) {
if(!safe(curX, curY+k) or inp[curX][curY+k]=='#' or cst[curX][curY+k][curD] != INF) continue;
// 바로 옆에 D인 경우
if(curX*M+curY+k == ed) {
cst[curX][curY+k][curD] = cst[curX][curY][curD];
dq.push_front({curX*M+curY+k, curD});
}
// 바로 옆에 없는 경우
else {
pos = getPos(curX, curY+k, f);
if(pos == -1 or cst[pos/M][pos%M][curD] <= cst[curX][curY][curD]) continue;
cst[pos/M][pos%M][curD] = cst[curX][curY][curD];
dq.push_front({pos, curD});
}
}
// 중력 변환
pos = getPos(curX, curY, -f);
if(pos == -1 or cst[pos/M][pos%M][1-curD] <= cst[curX][curY][curD]+1) continue;
cst[pos/M][pos%M][1-curD] = cst[curX][curY][curD]+1;
dq.push_back({pos, 1-curD});
}
ret = min(cst[ed/M][ed%M][0], cst[ed/M][ed%M][1]);
}
// 출력
if(ret == INF) printf("-1");
else printf("%d", ret);
}
/*
6 5
.#...
#.#.#
#D.##
#...#
...C#
##.##
ans: 1
*/
|
cs |
후기
기본적인 0-1 BFS 탐색 기법을 활용한 문제입니다. 0-1 BFS 탐색은 다익스트라 알고리즘과 유사한 점이 있기에 연관지어 학습하면 좋을 듯 합니다. BFS 탐색을 좀 더 심도 있게 공부하고 싶은 사람에게 추천하고 싶은 문제입니다.
'문제 노트 > 백준' 카테고리의 다른 글
| 보안 업체( BOJ 9938 ) (0) | 2023.05.05 |
|---|---|
| 소가 길을 건너간 이유( BOJ 14469 ) (0) | 2023.05.05 |
| Contact( BOJ 1013 ) (0) | 2022.09.27 |
| 네온 사인( BOJ 8907 ) (0) | 2022.09.13 |
| 전구와 스위치( BOJ 2138 ) (0) | 2022.09.12 |