2917 늑대 사냥꾼

N*M 크기의 맵에서 V->J로 조건을 만족하며 이동했을 때 경로에 있는 risk 중 최소값을 출력하는 문제다.

risk는 입력을 받을 때 queue에 넣어놓고 bfs돌리면 쉽게 얻을 수 있다.

처음에는 순차적으로 증가하는 risk 특성을 이용하여 deque를 사용하려 했으나 나무의 배치에 따라 현재위치 +1,+0,-1 세가지 경우가 나오므로 그냥 priority_queue를 이용하여 리스크가 큰 곳부터 뽑아내어 갱신하다가 J에 도달하면 그동안 계산해왔던 min값을 출력하는 방법을 썼다.

처음에 입력받을 때 +, V 걸러준 후 else if가 아닌 else로 J위치 지정('.'에도 반응한다...)하는 멍청한 짓을 해서 한번 틀렸다.

<코드>

#include <stdio.h>
#include <string>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
 
typedef pair<int, int> pii;
 
int n, m, sx, sy, tx, ty, dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
int a[501][501];
 
int main() {
    memset(a, -1, sizeof(a));
    ios::sync_with_stdio(false);
    cin >> n >> m;
    queue<pii> q;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == '+') a[i][j] = 0, q.push({ i,j });
            else if (s[j] == 'V') sx = i, sy = j;
            else if(s[j] == 'J') tx = i, ty = j;
        }
    }
    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m || a[nx][ny] != -1) continue;
            a[nx][ny] = a[x][y] + 1;
            q.push({ nx,ny });
        }
    }
    // 순서 : 현재 노드의 risk, 타고온 경로에서의 risk 최소값, {좌표}
    priority_queue<pair<int, pair<int, pii>>> q2;
    q2.push({ a[sx][sy], {a[sx][sy],{sx,sy}} });
    while (q2.size()) {
        int x = q2.top().second.second.first;
        int y = q2.top().second.second.second;
        int c = q2.top().first;
        int mi = q2.top().second.first;
        q2.pop();
        if (a[x][y] == -1) continue;    // risk 배열 재활용. -1 : visited
        a[x][y] = -1;
        if (x == tx && y == ty) {
            printf("%d", mi);
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m || a[nx][ny] == -1) continue;
            q2.push({ a[nx][ny],{min(a[nx][ny],mi),{nx,ny}} });
        }
    }
    return 0;
}