문제 : https://www.acmicpc.net/problem/1194
비트마스킹 BFS 그래프탐색
[문제해석]
'0' 지점에서 '1' 지점까지 탐색을 진행하는데 'a','b','c','d','e','f' 는 열쇠고 'A','B','C','D','E','F'는 각각 소문자 열쇠로 열 수 있는 문이다. 문을 열려면 열쇠가 있는 지점을 먼저 방문해서 열쇠를 가지고 방문해야된다.
[알고리즘풀이]
전형적인 비트마스킹을 활용한 그래프 탐색 문제로 열쇠가 6 종류 밖에 없는 점에 집중해 비트마스킹으로 현재 어떤 열쇠들을 가지고 있는지 표현해주면 된다.
visited[X][Y][curS] := (X, Y) 지점에 curS 열쇠 상태로 방문했을 때 최소 이동 횟수 라고 정의하면 문제를 쉽게 해결할 수 있다.
1) 다음에 이동할 지점이 '.' 거나 '1' 이면 현재 이동 횟수 + 1 이 해당 지점에 현재 상태로 방문한 가장 작은 값이라면 이동을 진행한다.
2) 다음에 이동할 지점이 열쇠가 있고 현재 이동 횟수 + 1 이 해당 지점에 현재 상태로 방문한 가장 작은 값이라면 이동을 진행한다. 그 후, 현재 상태에 해당 지점의 열쇠를 갱신해준다.
| (OR) 연산을 이용하면 쉽게 갱신할 수 있다.
( curS | (1 << key) )
3) 다음에 이동할 지점이 문이 있고 현재 이동 횟수 + 1 이 해당 지점에 현재 상태로 방문한 가장 작은 값이고, 현재 열쇠 상태가 해당 문을 열 수 있다면 이동을 진행한다.
& (AND) 연산을 이용하면 현재 열쇠 상태로 문을 열 수 있는지 쉽게 확인할 수 있다.
( curS & (1 << door) )
[ 주의사항 ]
열쇠가 총 6종류 이므로 비트마스킹을 (1 << 7) 로 진행해야되는데, (1 << 6) 으로 셋팅해서 개고생을 했다....! 조심, 또 조심!
[ 정답코드 ]
|
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
|
#include<iostream>
#include<queue>
using namespace std;
struct position {
int x, y, s, l;
};
const int INF = 9999999;
int r, c;
int visited[50][50][1 << 7];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
char map[50][51];
bool checkIndex(int x, int y) {
return (0 <= x && x < r && 0 <= y && y < c);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> r >> c;
for (int i = 0; i < r; i++)
cin >> map[i];
for (int i = 0; i < r; i++) // 초기화
for (int j = 0; j < c; j++)
for (int k = 0; k < (1 << 7); k++)
visited[i][j][k] = INF;
queue<position> q;
for (int i = 0; i < r; i++) // 시작점 찾기
for (int j = 0; j < c; j++)
if (map[i][j] == '0') {
visited[i][j][0] = 0;
q.push({ i, j, 0, 0 });
map[i][j] = '.';
}
while (!q.empty()) { // 탐색진행
int curX = q.front().x, curY = q.front().y, curS = q.front().s, curL = q.front().l;
q.pop();
if (map[curX][curY] == '1') continue;
for (int i = 0; i < 4; i++) {
int nextX = curX + dx[i], nextY = curY + dy[i];
if (!checkIndex(nextX, nextY)) continue;
if (map[nextX][nextY] == '#') continue;
if ((map[nextX][nextY] == '.' || map[nextX][nextY] == '1') && curL + 1 < visited[nextX][nextY][curS]) { // 그냥 갈 수 있는 길
visited[nextX][nextY][curS] = curL + 1;
q.push({ nextX, nextY, curS, curL + 1 });
}
else if ('a' <= map[nextX][nextY] && map[nextX][nextY] <= 'f' && curL + 1 < visited[nextX][nextY][curS]) {
int key = (map[nextX][nextY] - 'a') + 1;
visited[nextX][nextY][curS] = curL + 1;
q.push({ nextX, nextY, curS | (1 << key), curL + 1 });
}
else if ('A' <= map[nextX][nextY] && map[nextX][nextY] <= 'F' && curL + 1 < visited[nextX][nextY][curS]) {
int door = (map[nextX][nextY] - 'A') + 1;
if (curS & (1 << door)) {
visited[nextX][nextY][curS] = curL + 1;
q.push({ nextX, nextY, curS, curL + 1 });
}
}
}
}
int ans = INF; // '1' 인 지점에 방문한 값 중 최소값 찾기
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
if (map[i][j] == '1')
for (int k = 0; k < (1 << 7); k++)
ans = min(ans, visited[i][j][k]);
if (ans == INF) ans = -1;
cout << ans << '\n';
}
|
cs |
'Problem Solving > BOJ' 카테고리의 다른 글
| [BOJ] 2517 : 달리기 (0) | 2020.08.14 |
|---|---|
| [BOJ] 10167 : 금광 (0) | 2020.08.13 |
| [BOJ] 17025 : Icy Perimeter (0) | 2020.07.30 |
| [BOJ] 15898 : 피아의 아틀리에 ~신비한 대회의 연금술사~ (0) | 2020.07.27 |
| [BOJ] 15906 : 변신 이동 게임 (0) | 2020.07.06 |
