17836번: 공주님을 구해라!
용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는
www.acmicpc.net
시작점 : (1, 1)
도착점 : (N, M)
제한 시간 : T
무기가 없으면 벽을 지나갈 수 없지만 무기가 있으면 모든 벽을 부수고 지나갈 수 있습니다.
visit[x][y][chk] : x, y에 도달했을 때 무기를 가진 상태로 방문했는지 여부
1. 다음 칸이 무기가 있는 칸일 경우(list[nx][ny] = 2)
- 무기를 획득하였으므로 chk=true인 값을 큐에 넣어줍니다.
2. 다음 칸이 벽이 아니고 방문하지 않았을 경우
- 평상시 bfs처럼 다음 정점을 큐에 넣고 방문체크합니다.
3. 다음 칸이 벽이고 무기를 가진 상태인 경우
- 무기를 갖고있으면 어디든 지나갈 수 있으므로 2번과 같은 로직을 수행합니다.
도착지점인 (N, M)의 값은 0이므로 2, 3번에서 (N, M)에 도달하였으면 현재 시간을 출력합니다.
만약 T시간 동안 (N, M)에 도달하지 못하면 Fail을 출력합니다.
|
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
|
#include <iostream>
#include <queue>
using namespace std;
typedef struct Point {
int x;
int y;
bool chk;
};
queue<Point> q;
bool visit[101][101][2];
int list[101][101];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, T;
void bfs() {
q.push({ 1,1,false });
visit[1][1][0] = true;
for (int t = 1; t <= T; t++) {
int qsize = q.size();
while (qsize--) {
int x = q.front().x;
int y = q.front().y;
bool chk = q.front().chk;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
if (list[nx][ny] == 2 && !visit[nx][ny][1]) {
q.push({ nx,ny,true });
visit[nx][ny][1] = true;
}
else if (list[nx][ny] == 0 && !visit[nx][ny][chk]) {
q.push({ nx,ny,chk });
visit[nx][ny][chk] = true;
if (nx == N && ny == M) {
cout << t << '\n';
return;
}
}
else if (list[nx][ny] == 1 && chk && !visit[nx][ny][chk]) {
q.push({ nx,ny,chk });
visit[nx][ny][chk] = true;
if (nx == N && ny == M) {
cout << t << '\n';
return;
}
}
}
}
}
cout << "Fail\n";
}
void input() {
cin >> N >> M >> T;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> list[i][j];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
bfs();
return 0;
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 2573 빙산 (0) | 2021.04.05 |
|---|---|
| boj 14923 미로 탈출 (0) | 2021.03.29 |
| boj 9205 맥주 마시면서 걸어가기 (0) | 2021.03.25 |
| boj 1600 말이 되고픈 원숭이 (0) | 2021.03.24 |
| boj 2589 보물섬 (0) | 2021.03.16 |