BOJ 11952 - 좀비 링크
(2023.05.26 기준 G2)

문제

N개의 도시와 M개의 도로로 이루어진 도시 중에서 K개의 도시가 좀비에게 점령당했다.
좀비에게 점령당한 도시로부터 S번 이하의 이동으로 이동할 수 있는 모든 도시는 위험한 도시로 정의되며, 안전한 도시의 숙박비는 p원, 위험한 도시의 숙박비는 q원이다.
각 도시를 이동할 때마다 1박을 해야하며, 좀비에게 점령당한 도시에선 숙박을 할 수 없을 때, 1번 도시에서 N번 도시로 이동하는 데 드는 최소 비용 출력

알고리즘

S번 이하의 이동은 BFS. 숙박비를 가중치로 둔 그래프에서의 최소 비용은 다익스트라.

풀이

일단 도시마다 위험도를 부여하자. 0은 안전한 도시, 1은 위험한 도시, 2는 좀비에게 점령당한 도시. 그리고 좀비에게 점령당한 도시로부터 이동 거리가 S가 될 때까지 BFS를 돌리면 된다. 이렇게 하면 방문체크는 저절로 위험도로 가능해진다.

이제 1번 도시에서의 최단 거리를 다익스트라로 구하면 된다.
굳이, 다시 그래프를 만들 필요는 없고, 다음에 갈 도시의 위험도에 따라 비용을 설정해서 비교하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const ll inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M, K, S, p, q;
    cin >> N >> M >> K >> S >> p >> q;

    int risk[N]; fill(risk, risk + N, 0); // 0 : 안전, 1 : 위험, 2 : 좀비
    deque<pii> dq; // deque for bfs
    for (int _ = 0, i; _ < K; _++){
        cin >> i;
        risk[--i] = 2;
        dq.push_back({i, 0});
    }

    vector<int> graph[N];
    for (int _ = 0, i, j; _ < M; _++){
        cin >> i >> j;
        graph[--i].push_back(--j);
        graph[j].push_back(i);
    }

    // 위험한 도시 체크
    while (!dq.empty()){
        auto [i, s] = dq.front(); dq.pop_front();
        if (s == S) // 최대 범위에 도달했다면 멈춘다.
            continue;
        for (int j: graph[i]){
            if (risk[j]) // 이미 체크한 도시는 패스
                continue;
            risk[j] = 1;
            dq.push_back({j, s + 1});
        }
    }

    // 다익스트라
    ll dist[N];
    dist[0] = 0; fill(dist + 1, dist + N, inf);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, 0});
    while (!pq.empty()){
        auto [d, i] = pq.top(); pq.pop();
        if (dist[i] < d) continue;
        for (int j: graph[i]){
            ll cost = (risk[j]) ? ((risk[j] == 1) ? q : inf) : p;
            if (dist[j] > d + cost){
                dist[j] = d + cost;
                pq.push({dist[j], j});
            }
        }
    }

    cout << dist[N - 1] - ((risk[N - 1]) ? q : p);
}

• Python

import sys; input = sys.stdin.readline
from math import inf
from heapq import heappop, heappush
from collections import deque

N, M, K, S = map(int, input().split())
p, q = map(int, input().split())

risk = [0] * N # 0 : 안전, 1 : 위험, 2 : 좀비
dq = deque() # deque for bfs
for _ in range(K):
    i = int(input()) - 1
    risk[i] = 2
    dq.append((i, 0))

graph = [[] for _ in range(N)]
for _ in range(M):
    i, j = map(int, input().split())
    i -= 1; j -= 1
    graph[i].append(j)
    graph[j].append(i)

# 위험한 도시 체크
while dq:
    i, s = dq.popleft()
    if s == S: # 최대 범위에 도달했다면 멈춘다.
        continue
    for j in graph[i]:
        if risk[j]: # 이미 체크한 도시는 패스
            continue
        risk[j] = 1
        dq.append((j, s + 1))

# 다익스트라
dist = [inf] * N
dist[0] = 0
pq = [(0, 0)]
while pq:
    d, i = heappop(pq)
    if dist[i] < d:
        continue
    for j in graph[i]:
        cost = p if risk[j] == 0 else q if risk[j] == 1 else inf
        if dist[j] > d + cost:
            dist[j] = d + cost
            heappush(pq, (dist[j], j))

print(dist[N - 1] - (p if risk[N - 1] == 0 else q))