https://www.acmicpc.net/problem/22944
1. 상하좌우로 이동한다. 만약 이동할 곳이 격자 밖이라면 이동할 수 없다.
2. 이동한 곳이 안전지대라면 반복을 종료한다.
3. 이동한 곳에 우산이 있다면 우산을 든다. 만약, 이동할 때부터 우산을 가지고 있다면 가지고 있는 우산을 버리고 새로운 우산으로 바꾼다.
버린 우산은 더 이상 사용할 수 없다.
4. 죽음의 비를 맞았을 때, 우산을 가지고 있다면 우산의 내구도가 1이 감소하고 만약 우산을 가지고 있지 않는다면 체력이 1 감소한다.
5. 만약 우산의 내구도가 0이 되면 들고 있는 우산이 사라진다.
6. 만약 체력이 0이 되면 죽는다.
7. 아직 체력이 남았다면 안전지대까지 위 과정을 반복한다.
격자 내 움직임은 위와 같은 순서로 진행됩니다.
S에서 출발하여 안전지대인 E로 도착하는 최소 거리를 구하는 문제입니다.
그리고 S에도 출발하는 직후부터는 비가 내린다고 명시되어 있습니다.
현재 체력 H와 우산의 내구도 D가 주어지며, 격자 내에는 우산이 놓여진 곳이 있습니다.
우선 최소거리를 구하기 위해 bfs를 사용합니다.
그리고 다음 좌표를 이동할 수 있는지 확인합니다.
내구도 1 이상인 U인 지점은 우산이 있고, 도착 지점인 E는 비가 오지 않으므로 무조건 지나갈 수 있습니다.
나머지 지점은 비가 오기 때문에 체력이 1보다는 많아야 지나갈 수 있습니다. (정확하게는 체력 + 들고 있는 우산의 남은 내구도)
U가 있는 지점에 도착한다면 우산의 내구도를 D로 초기화 해주시고, E가 아닌 모든 지점에서 우산의 내구도 or 체력을 1씩 감소시킵니다.
그리고 남은 체력 + 들고있는 우산의 내구도가 visit[nx][ny]보다 큰지 비교합니다.
해당 지점을 방문했더라도 체력의 상태가 다르기 때문에 방문처리를 int로 하게 되었습니다.
visit[nx][ny] >= nh + nu이면, 이전 단계보다 좋지 않은 조건으로 이동하는거라 제외를 시켜주시면 되고, 해당 visit 배열을 더 큰 값으로 갱신시켜주도록 합니다.
(중간에 체력이 0이 되었어도 visit 배열 자체가 0으로 초기화되어 있기 때문에 자동으로 걸러집니다.)
이 과정을 반복하여 E에 도착했다면 t를 리턴시켜주고, 반복문이 종료되어도 답을 구하지 못했다면 지나갈 수 없다는 뜻이므로 -1을 리턴해줍니다.
|
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
|
#include <iostream>
#include <queue>
#define MAX 501
using namespace std;
typedef pair<int, int> pii;
char list[MAX][MAX];
int visit[MAX][MAX];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, H, D;
int sx, sy;
bool isMove(int x, int y, int hd) {
if (list[x][y] == 'U' || list[x][y] == 'E') return true;
return hd > 1;
}
int bfs() {
queue<pair<pii, pii> > q;
q.push({ {H, 0}, {sx, sy} });
visit[sx][sy] = H;
for (int t = 0; !q.empty(); t++) {
int qsize = q.size();
while (qsize--) {
int x = q.front().second.first;
int y = q.front().second.second;
int h = q.front().first.first;
int u = q.front().first.second;
q.pop();
if (list[x][y] == 'E') {
return t;
}
for (int d = 0; d < 4; d++) {
int nx = x + direct[d][0];
int ny = y + direct[d][1];
int nh = h;
int nu = u;
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (!isMove(nx, ny, h + u)) continue;
if (list[nx][ny] == 'U') {
nu = D;
}
if (list[nx][ny] != 'E') {
if (nu) nu--;
else nh--;
}
if (visit[nx][ny] >= nh + nu) continue;
q.push({ {nh, nu}, {nx,ny} });
visit[nx][ny] = nh + nu;
}
}
}
return -1;
}
void func() {
cout << bfs() << '\n';
}
void input() {
cin >> N >> H >> D;
for (int i = 0; i < N; i++) {
cin >> list[i];
for (int j = 0; j < N; j++) {
if (list[i][j] == 'S') {
sx = i;
sy = j;
}
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 27211 도넛 행성 (2) | 2024.07.17 |
|---|---|
| boj 19940 피자 오븐 (0) | 2024.07.16 |
| boj 2310 어드벤처 게임 (0) | 2024.06.25 |
| boj 2412 암벽 등반 (0) | 2024.06.22 |
| boj 14497 주난의 난(難) (0) | 2024.06.21 |