알고리즘 풀이/BFS(너비 우선 탐색)
BOJ 17836 [공주님을 구해라!]
갓우태
2021. 3. 7. 23:00
BOJ 공주님을 구해라! : www.acmicpc.net/problem/17836
17836번: 공주님을 구해라!
용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는
www.acmicpc.net
간단한 BFS 문제이다.
키포인트는 방문배열(visit)를 3차원으로 설정했다.
visited[3][3][0] => 그람 없이 (3, 3)을 방문한 경우
visited[3][3][1] => 그람을 가지고 (3, 3)을 방문한 경우
그람을 획득하면, 해당 node가 그람을 가지도록 체크해준다.
|
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
|
#include <iostream>
#include <queue>
using namespace std;
int N, M, T;
bool visited[100][100][2];
int map[100][100];
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };
class Node
{
public:
int x, y, time;
int gram;
Node(int x, int y, int time, int gram)
{
this->x = x;
this->y = y;
this->time = time;
this->gram = gram;
}
};
queue<Node> q;
bool IsBoundary(int x, int y)
{
return x >= 0 && x < N && y >= 0 && y < M;
}
int Bfs()
{
q.push(Node(0, 0, 0, false));
visited[0][0][0] = true;
while (!q.empty())
{
Node node = q.front();
q.pop();
if (node.time > T)
{
return 0;
}
if (node.x == N - 1 && node.y == M - 1)
{
return node.time;
}
for (int i = 0; i < 4; i++)
{
int nextX = node.x + dx[i];
int nextY = node.y + dy[i];
if (IsBoundary(nextX, nextY))
{
switch (map[nextX][nextY])
{
case 0:
if (!visited[nextX][nextY][node.gram])
{
visited[nextX][nextY][node.gram] = true;
q.push(Node(nextX, nextY, node.time + 1, node.gram));
}
case 1:
if (node.gram == 1)
{
if (!visited[nextX][nextY][1])
{
visited[nextX][nextY][1] = true;
q.push(Node(nextX, nextY, node.time + 1, node.gram));
}
}
break;
case 2:
if (!visited[nextX][nextY][1])
{
visited[nextX][nextY][1] = true;
q.push(Node(nextX, nextY, node.time + 1, 1));
}
break;
}
}
}
}
return 0;
}
int Solution_17836()
{
cin.tie(0);
ios::sync_with_stdio(0);
cin >> N >> M >> T;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> map[i][j];
}
}
int result = Bfs();
if (result == 0)
{
cout << "Fail";
}
else
{
cout << result;
}
return 0;
}
|
cs |
반응형