백준(BOJ) 11952 좀비(Python)

문제 내용

 

BFS와 다익스트라를 사용한 문제.

위험한 도시를 구하기 위해 좀비에게 점령당한 도시에서 BFS를 돌리고, 그 후 1번 도시에서 다익스트라를 돌려 N번 도시로의 최소 비용을 구한다.

일반적인 다익스트라와는 달리 간선에 가중치를 두는 것이 아닌, 도착한 노드의 타입에 따라 비용을 더하는 방식으로 다익스트라를 진행했다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,m,k,s=map(int,input().split())
p,q=map(int,input().split())
L=[p for i in range(n+1)]
X=[int(input()) for i in range(k)]
D=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    D[a].append(b)
    D[b].append(a)

for i in X:
    visited=[0 for i in range(n+1)]
    queue=deque()
    queue.append([i,0])
    visited[i]=1
    while queue:
        a,b=queue.popleft()
        if b<=s:
            L[a]=q
            for j in D[a]:
                if not visited[j]:
                    queue.append([j,b+1])
                    visited[j]=1
L[1]=0
L[n]=0
dist=[sys.maxsize for i in range(n+1)]
dist[1]=0
queue=[]
heapq.heappush(queue,[0,1])
while queue:
    a,b=heapq.heappop(queue)
    if dist[b]<a:
        continue
    for i in D[b]:
        if i in X:
            continue
        nd=dist[b]+L[i]
        if nd<dist[i]:
            dist[i]=nd
            heapq.heappush(queue,[nd,i])
print(dist[n])

 

BFS에서 visited 갱신을 빼먹어서 시간 초과가 터졌다.

뭐지 싶어서 한참 고민했다.

좀비가 점령한 도시는 다익스트라에서 방문하지 않아야 하는데, 문제를 제대로 안 보고 풀어서 답이 이상하게 나오는 걸 보고 뒤늦게 알아챘다.

아직 디테일이 부족하다.