BOJ 11952 - 좀비

문제

백준 온라인 저지 - 11952번

풀이 과정

문제에서 주어진 좀비로 점령된 도시들을 이용해서 위험한 지역을 찾고,

이를 통해 도시 방문 비용을 계산하고 다익스트라 알고리즘을 이용해 최단거리를 계산합니다.

이때 도시에게 점령당한 도시는 최단 거리 계산 시 고려하지 않도록 하는 것에 유의합니다.

좀비에게 점령당한 도시를 기준으로 S 이하의 거리를 가지는 위험한 도시를 판단하기 위해서는 BFS 를 이용했습니다.

코드

import sys
from collections import deque
import heapq

N, M, K, S = list(map(int, sys.stdin.readline().split()))
P, Q = list(map(int, sys.stdin.readline().split()))
occupied = [int(sys.stdin.readline().strip()) for _ in range(K)]
edges = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]


def make_graph():
    graph = [[] for _ in range(N + 1)]

    for frm, to in edges:
        graph[frm].append(to)
        graph[to].append(frm)

    return graph


def find_zombie_land(graph):
    zombie_land = [0] * (N + 1)

    for start in occupied:
        lands = bfs(start, graph, S)
        for land in lands:
            zombie_land[land] = 1

    zombie_land[1] = 0
    zombie_land[N] = 0

    return zombie_land


def bfs(start, graph, offset):
    visit = [0] * (N + 1)
    q = deque()

    ret = []
    visit[start] = 1
    q.append([start, 0])

    while q:
        here, move = q.popleft()

        if move > offset:
            continue
        else:
            ret.append(here)

        for there in graph[here]:
            if not visit[there]:
                visit[there] = 1
                q.append([there, move + 1])

    return ret


def dijkstra(graph, zombie_land):
    pq = []
    dist = [sys.maxsize] * (N + 1)

    dist[1] = 0
    heapq.heappush(pq, [0, 1])

    while pq:
        cost, here = heapq.heappop(pq)

        if dist[here] < cost:
            continue

        for there in graph[here]:
            if there in occupied:
                continue

            next_cost = cost + (Q if zombie_land[there] else P)
            if next_cost < dist[there]:
                dist[there] = next_cost
                heapq.heappush(pq, [next_cost, there])

    return dist[N] - P


def solution():
    graph = make_graph()
    zombie_land = find_zombie_land(graph)
    answer = dijkstra(graph, zombie_land)

    return answer


print(solution())