[백준] 17396 백도어

문제

• 총 N개의 분기점과 분기점을 잇는 M개의 길이 있고, 각 길을 통과하는데 t 시간이 걸린다.
  • 1 <= N <= 100,000
  • 1 <= M <= 300,000
  • 1 <= t <= 100,000
• 각 분기점에 위치한 와드/미니언/포탑 등 상대의 시야에 걸리는 곳을 피해야한다.
  • 각 분기점이 적의 시야에 보이는지 주어진다.
• 0번에서 시작해 넥서스의 위치 N-1번 까지 갈 수 있는 최소 시간 구하기
• 갈 수 없으면 -1 출력하기

 

풀이

• 갈 수 없는 노드를 제외해 최단 경로 구하기
• 다익스트라 사용
• 시간 복잡도 : O(ElogV) 가능!

 

import heapq
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
observer = list(map(int, input().split()))  # 적 시야에 보이는지 여부
# 갈 수 없는 노드 정리하기 (마지막 N-1번째 노드는 제외!)
observer = set([i for i, x in enumerate(observer[:-1]) if x == 1])
# 지도 입력받기
graph = [ [] for _ in range(N)]
for _ in range(M):
    a, b, t = map(int, input().split())
    # 갈 수 없는 노드면 지도에 추가하지 않는다
    if a not in observer and b not in observer :     
        graph[a].append((b, t))
        graph[b].append((a, t))

# 다익스트라
INF = sys.maxsize
distance = [INF] * N        # 최단 거리 테이블
q = []          
heapq.heappush(q, (0, 0))   # (비용, 출발 노드) 넣기
distance[0] = 0             # 출발 노드의 비용은 0

while q:
    dist, now = heapq.heappop(q)

    # 이미 처리된 경우 제외
    if distance[now] < dist :
        continue

    for i in graph[now]:
        cost = dist + i[1]
        # 현재 노드를 거쳐 가는 경로가 최단 경로인 경우 업데이트
        if cost < distance[i[0]]:
            distance[i[0]] = cost
            heapq.heappush(q, (cost, i[0]))

print(-1) if distance[N-1] == INF else print(distance[N-1])

 

References

• 백준 17396번
• 2023.04.24 오늘의 문제