늑대 현우가 사냥꾼을 피하여 가장 안전한 경로로 도망칠 때
나무와 현우와의 거리 중 최솟값을 구하는 문제입니다.
어느 나무에 사냥꾼이 있을지 모르기 때문에 모든 나무에 사냥꾼이 있다는 가정하에 거리를 구해야 합니다.
각 구역에서 가장 가까운 나무와의 최소 거리를 구해야 합니다.
각 나무들을 동시에 BFS를 하여 각 구역의 최소 거리를 구하겠습니다.
각 나무들의 좌표를 큐에 넣고 BFS를 하여 방문한 좌표는 거리를 저장해 주고
나중에 같은 좌표를 방문하더라도 거리가 같거나 멀기 때문에 무시해 주시면 됩니다.
최소 거리들을 다 구해줬으면 이제 가능한 경로 중에 가장 안전한 경로를 구하기 위해 경로 중에 나무와의 최소 거리가 최댓값인 경로를 구하면 됩니다.
최대 경로를 구하기 위해 다 엑스트라를 구현하겠습니다.
현우가 위치한 좌표부터 갈 수 있는 방향으로 가면서 나무와의 거리를 최대 힙 우선순위 큐에 넣어줍니다.
그리고 다음 좌표로 우선순위 큐에서 최댓값을 받아서 정해줍니다.
우선순위 큐에 값을 저장할 때는 시작점부터 지금까지 경로 중에 나무와의 거리의 최솟값을 넣어주면 됩니다.
그렇게 하게 되면 우선순위 큐가 최대로 구해주기 때문에 가장 안전한 경로를 구할 수 있고 오두막에 도착했다면 우선순위 큐에 있는 거리와
오두막과 나무와의 최소 거리 중 최솟값을 출력해 주시면 됩니다.
뻔한 다익스트라 그대로 구현하면 되는 문제랑 살짝 다르지만 그래도 기본 틀에서 크게 바뀌지 않았습니다.
다익스트라를 돌리면서 최솟값을 잘 넣어주면 문제없이 풀 수 있습니다!
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i, a, b) for(int i=a;i<=b;i++)
#define vi vector <int>
#define vvi vector <vi>
#define pii pair <int,int>
#define fs first
#define sd second
#define ep emplace
using namespace std;
int main() {
FIO;
int n, m; cin >> n >> m;
char map[505][505];
queue <pii> q;
vvi dist, dp;
dist = dp = vvi(n + 1, vi(m + 1, -1));
int sr, sc;
FOR(i, 1, n) FOR(j, 1, m) {
cin >> map[i][j];
if (map[i][j] == '+') q.ep(i, j), dist[i][j] = 0;
if (map[i][j] == 'V') sr = i, sc = j;
}
int dir[4][2] = { {-1,0}, {0,-1},{1,0},{0,1} };
auto bfs = [&]() {
while (q.size()) {
pii now = q.front(); q.pop();
for (auto d : dir) {
int nr = d[0] + now.fs, nc = d[1] + now.sd;
if (nr < 1 || nc < 1 || nr > n || nc > m) continue;
if (dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[now.fs][now.sd] + 1;
q.ep(nr, nc);
}
}
};
bfs();
vvi visit(n + 1, vi(m + 1));
auto solve = [&]() {
priority_queue <pair <int, pii>> pq;
visit[sr][sc] = 1;
pq.ep(dist[sr][sc], pii(sr, sc));
while (pq.size()) {
auto now = pq.top(); pq.pop();
for (auto d : dir) {
int nr = d[0] + now.sd.fs, nc = d[1] + now.sd.sd;
if (nr < 1 || nc < 1 || nr > n || nc > m) continue;
if (visit[nr][nc]) continue;
visit[nr][nc] = 1;
if (map[nr][nc] == 'J') return min(now.fs, dist[nr][nc]);
pq.ep(min(now.fs, dist[nr][nc]), pii(nr, nc));
}
}
};
cout << solve() << '\n';
return 0;
}