|
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
|
#include <iostream>
#include <queue>
using namespace std;
struct pos {
int row, col, time;
};
int n, m, t;
char map[100][101];
int moveY[] = {-1, 1, 0, 0}, moveX[] = {0, 0, -1, 1};
int bfs() {
queue<pos> myQueue;
myQueue.push(pos{0, 0, 0});
bool visited[100][100] = {false};
while (!myQueue.empty()) {
int row = myQueue.front().row, col = myQueue.front().col, time = myQueue.front().time;
myQueue.pop();
if (row == n - 1 && col == m - 1) //공주님 위치에 도착
return time;
for (int i = 0; i < 4; i++) {
int newRow = row + moveY[i], newCol = col + moveX[i];
if (newRow < 0 || newRow >= n || newCol < 0 || newCol >= m)
continue;
if (map[newRow][newCol] != '1' && !visited[newRow][newCol]) {
myQueue.push(pos{newRow, newCol, time + 1});
visited[newRow][newCol] = true;
}
}
}
return 999999;
}
int findGram() {
queue<pos> myQueue;
myQueue.push(pos{0, 0, 0});
bool visited[100][100] = {false};
while (!myQueue.empty()) {
int row = myQueue.front().row, col = myQueue.front().col, time = myQueue.front().time;
myQueue.pop();
if (map[row][col] == '2') //그람을 찾음
return time + (n - 1 - row) + (m - 1 - col); //벽 깨고 공주님 위치에 도착
for (int i = 0; i < 4; i++) {
int newRow = row + moveY[i], newCol = col + moveX[i];
if (newRow < 0 || newRow >= n || newCol < 0 || newCol >= m)
continue;
if (map[newRow][newCol] != '1' && !visited[newRow][newCol]) {
myQueue.push(pos{newRow, newCol, time + 1});
visited[newRow][newCol] = true;
}
}
}
return 999999;
}
int main() {
cin >> n >> m >> t;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> map[i][j];
int ans = min(bfs(), findGram());
if (ans <= t)
cout << ans << '\n';
else
cout << "Fail" << '\n';
return 0;
}
|
cs |
단순 BFS로 도착하는 경우와 그람을 찾아서 벽을 깨고 도착하는 경우를 고려해서 풀면 된다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 20951 유아와 곰두리차 (0) | 2021.02.23 |
|---|---|
| 백준 온라인 저지 1025 제곱수 찾기 (0) | 2021.02.20 |
| 백준 온라인 저지 12789 도키도키 간식드리미 (0) | 2021.02.10 |
| 백준 온라인 저지 1744 수 묶기 (0) | 2021.02.06 |
| 백준 온라인 저지 1992 쿼드트리 (0) | 2021.02.05 |
