[백준] 2917 - 늑대 사냥꾼

https://www.acmicpc.net/problem/2917

N, M제한이 500이기 때문에, 지도의 모든 곳을 탐색하면서 동시에 가장 가까운 나무와의 거리를 구하는 것은 최대 500 ^ 4의 시간이 걸릴 것이다. 따라서 지도의 각 부분에서 어떻게 하면 가장 가까운 나무와의 거리를 빠르게 구할 수 있는지 생각해야 한다.

 

그렇다면 각 나무에서 빈 목초지까지 거리를 구하면 어떨까? 그런데 이 방법은 더 가까운 나무가 생길수록 빈 목초지의 내용이 계속 갱신될 것이다. 이 부분은 BFS를 통해서 해결해 보자.

 

.....
.+..+
+....
...+.

이런 입력이 있다.

 

BFS를 이용하면 t = 1 일때 다음과 같다.

.1..1
1+11+
+1.11
1.1+1

 

t = 2 일때 다음과 같다.

21221
1+11+
+1211
121+1

 

따라서 이렇게 각 빈 목초지에 가중치 배열을 만들고 다익스트라로 답을 구하면 된다.

다익스트라를 할 때 주의할 점은, 우리는 보통 다익스트라를 사용할 때 최단 거리를 구한다. 하지만 이 문제는 우리가 만든 가중치 배열을 가지고 최소 가중치가 최대가 되게 경로를 구해야 한다는 것이다.

따라서 맨 처음 dis 배열을 0으로 초기화해주고, priority_queue도 최대힙으로 선언해 주어야 한다.

 

#include <iostream>
#include <queue>
using namespace std;

int n, m, sx, sy, ex, ey;
char map[500][500];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int vis[500][500];

int main() {
    cin >> n >> m;
    queue<pair<int, int>> t;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'V') {
                sx = i;
                sy = j;
                map[i][j] = '.';
            } else if (map[i][j] == 'J') {
                ex = i;
                ey = j;
                map[i][j] = '.';
            } else if (map[i][j] == '+') {
                t.push({i, j});
                vis[i][j] = 1;
            }
        }
    }
    while (!t.empty()) {
        int x = t.front().first;
        int y = t.front().second;
        t.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == '.' && !vis[nx][ny]) {
                vis[nx][ny] = vis[x][y] + 1;
                t.push({nx, ny});
            }
        }
    }
    vector<vector<pair<int, int>>> v(n * m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    v[i * m + j].push_back(
                        {nx * m + ny, min(vis[i][j], vis[nx][ny])});
                }
            }
        }
    }

    vector<int> dis(250000, 0);
    priority_queue<pair<int, int>> pq;
    dis[sx * m + sy] = vis[sx][sy];
    pq.push({vis[sx][sy], sx * m + sy});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int x = pq.top().second / m;
        int y = pq.top().second % m;
        pq.pop();

        if (x == ex && y == ey) {
            cout << cost - 1;
            break;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nxCost = min(cost, vis[nx][ny]);
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dis[nx * m + ny] < nxCost) {
                dis[nx * m + ny] = nxCost;
                pq.push({nxCost, nx * m + ny});
            }
        }
    }
}