16954 움직이는 미로탈출
알고리즘(BFS)
1
2
3
4
5
1. q와 nextq를 선언
2. q엔 현재 노드를 저장. 하나식 꺼내서 이동가능한 인접 칸을 nextq에 추가.
3. 다 추가하면, 벽을 한칸 내림
4. 이후 q에 nextq를 넣고, nextq는 비운채 다음 루프 시작.
5. 루프 중에 q에서 꺼낸 노드가 벽이 있는 칸이라면 추가안하고 다음 노드로, 최우측상단이라면 종료
코드
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
#include <bits/stdc++.h>
using namespace std;
char miro[8][8];
list<pair<int, int>> q, nextq;
bool visitcheck[8][8];
bool BFS();
int main() {
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
cin >> miro[i][j];
cout << BFS();
}
bool BFS() {
bool check = false;
nextq.push_back({ 7,0 });
while (!nextq.empty() && !check) {
q = nextq;
nextq.clear();
memset(visitcheck, 0, sizeof(visitcheck));
while (!q.empty()) {
int r = q.front().first, c = q.front().second;
q.pop_front();
if (miro[r][c] == '#')
continue;
if (r == 0 && c == 7) {
check = true;
break;
}
if (miro[r][c] != '#' && !visitcheck[r][c]) {
nextq.push_back({ r, c });
visitcheck[r][c] = true;
}
if (r > 0 && miro[r - 1][c] != '#' && !visitcheck[r - 1][c]) {
nextq.push_back({ r - 1,c });
visitcheck[r - 1][c] = true;
}
if (r > 0 && c < 7 && miro[r - 1][c + 1] != '#' && !visitcheck[r - 1][c + 1]) {
nextq.push_back({ r - 1,c + 1 });
visitcheck[r - 1][c + 1] = true;
}
if (c < 7 && miro[r][c + 1] != '#' && !visitcheck[r][c + 1]) {
nextq.push_back({ r, c + 1 });
visitcheck[r][c + 1] = true;
}
if (r < 7 && c < 7 && miro[r + 1][c + 1] != '#' && !visitcheck[r + 1][c + 1]) {
nextq.push_back({ r + 1,c + 1 });
visitcheck[r + 1][c + 1] = true;
}
if (r < 7 && miro[r + 1][c] != '#' && !visitcheck[r + 1][c]) {
nextq.push_back({ r + 1,c });
visitcheck[r + 1][c] = true;
}
if (r < 7 && c > 0 && miro[r + 1][c - 1] != '#' && !visitcheck[r + 1][c - 1]) {
nextq.push_back({ r + 1,c - 1 });
visitcheck[r + 1][c - 1] = true;
}
if (c > 0 && miro[r][c - 1] != '#' && !visitcheck[r][c - 1]) {
nextq.push_back({ r, c - 1 });
visitcheck[r][c - 1] = true;
}
if (r > 0 && c > 0 && miro[r - 1][c - 1] != '#' && !visitcheck[r - 1][c - 1]) {
nextq.push_back({ r - 1,c - 1 });
visitcheck[r - 1][c - 1] = true;
}
}
for (int i = 7; i > 1; i--)
for (int j = 0; j < 8; j++)
miro[i][j] = miro[i - 1][j];
for (int j = 0; j < 8; j++)
miro[0][j] = '.';
}
return check;
}