알고리즘/BOJ
[BOJ 18128, C++] 치삼이의 징검다리 건너기
70825
2021. 10. 1. 18:28
반응형
https://www.acmicpc.net/problem/18128
18128번: 치삼이의 징검다리 건너기
첫 번째 줄에 땅의 크기 N(3 ≤ N ≤ 1,000), 물 생성지 개수 W(1 ≤ W ≤ N)가 주어진다. 두 번째 줄부터 W+1줄까지 물의 생성 위치 x(행), y(열) (1 ≤ x, y ≤ N)가 주어진다. W+2줄부터 N개의 줄에
www.acmicpc.net
풀이
물 이동은 1초에 상하좌우 한 번씩 움직이므로 BFS로 만들 수 있습니다.
치삼이는 상하좌우와 대각선을 포함한 8개의 방향으로 움직일 수 있는데, 치삼이가 이동하는데 시간이 걸리지 않는다고 했으므로 치삼이가 도착할 수 있는 시간은 치삼이의 이동 경로중에 제일 늦게 식은 돌의 시간이 됩니다.
그래서 치삼이의 시간을 구하는 것은 다익스트라 알고리즘을 통해 구할 수 있게 됩니다.
주의할 점은 시작점과 도착점의 돌이 물에 닿지 않아도 된다는 것 입니다. 그래서 다익스트라를 시작할 때 출발돌이 식은 시간을 무시하고 돌리고, 도착할 때는 도착돌보다 도착점 주변의 돌중에 빨리 식은 돌이 있는지 찾아보면 됩니다.
코드
|
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
|
#include <iostream>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
using ll = long long;
const int N = 1001;
int n, w, x, y, S[N][N], visited[N][N], MAP[N][N];
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
int cx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, cy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
char k;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
memset(MAP, -1, sizeof(MAP));
memset(visited, -1, sizeof(visited));
memset(S, -1, sizeof(S));
queue<pair<int, int>> q;
priority_queue<pair<int, pair<int, int>>> pq;
cin >> n >> w;
for (int i = 0; i < w; i++) {
cin >> x >> y;
q.push(make_pair(--x, --y));
S[x][y] = 0;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> k;
MAP[i][j] = k - '0';
}
}
while (!q.empty()) {
pair<int, int> p = q.front(); q.pop();
int x = p.first, y = p.second;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (0 <= nx && nx < n && 0 <= ny && ny < n && S[nx][ny] == -1) {
S[nx][ny] = S[x][y] + 1;
q.push(make_pair(nx, ny));
}
}
}
pq.push(make_pair(0, make_pair(0, 0)));
while (!pq.empty()) {
pair<int, pair<int, int>> p = pq.top(); pq.pop();
int t = p.first, x = p.second.first, y = p.second.second;
if (x == n - 1 && y == n - 1) {
if (visited[x - 1][y] != -1) t = -min(-t, visited[x - 1][y]);
if (visited[x][y - 1] != -1) t = -min(-t, visited[x][y - 1]);
if (visited[x - 1][y - 1] != -1) t = -min(-t, visited[x - 1][y - 1]);
cout << -t << endl;
return 0;
}
for (int i = 0; i < 8; i++) {
int nx = x + cx[i], ny = y + cy[i];
if (0 <= nx && nx < n && 0 <= ny && ny < n && MAP[nx][ny] == 1 && visited[nx][ny] == -1) {
visited[nx][ny] = max(S[nx][ny], -t);
pq.push(make_pair(-visited[nx][ny], make_pair(nx, ny)));
}
}
}
cout << -1;
}
|
cs |
반응형