[BOJ | Python] 17396번: 백도어

https://www.acmicpc.net/problem/17396

 

문제

유섭이는 무척이나 게으르다. 오늘도 할 일을 모두 미뤄둔 채 열심히 롤을 하던 유섭이는 오늘까지 문제를 내야 한다는 사실을 깨달았다. 그러나 게임은 시작되었고 지는 걸 무척이나 싫어하는 유섭이는 어쩔 수 없이 백도어를 해 게임을 최대한 빠르게 끝내기로 결심하였다.

최대한 빨리 게임을 끝내고 문제를 출제해야 하기 때문에 유섭이는 최대한 빨리 넥서스가 있는 곳으로 달려가려고 한다. 유섭이의 챔피언은 총 N개의 분기점에 위치할 수 있다. 0번째 분기점은 현재 유섭이의 챔피언이 있는 곳을, N-1 번째 분기점은 상대편 넥서스를 의미하며 나머지 1, 2, ..., N-2번째 분기점은 중간 거점들이다. 그러나 유섭이의 챔피언이 모든 분기점을 지나칠 수 있는 것은 아니다. 백도어의 핵심은 안 들키고 살금살금 가는 것이기 때문에 적 챔피언 혹은 적 와드(시야를 밝혀주는 토템), 미니언, 포탑 등 상대의 시야에 걸리는 곳은 지나칠 수 없다.

입력으로 각 분기점을 지나칠 수 있는지에 대한 여부와 각 분기점에서 다른 분기점으로 가는데 걸리는 시간이 주어졌을 때, 유섭이가 현재 위치에서 넥서스까지 갈 수 있는 최소 시간을 구하여라.

 

입력

첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)

두 번째 줄에 각 분기점이 적의 시야에 보이는지를 의미하는 N개의 정수 a0, a1, ..., aN-1가 공백으로 구분되어 주어진다. ai가 0이면 i 번째 분기점이 상대의 시야에 보이지 않는다는 뜻이며, 1이면 보인다는 뜻이다. 추가적으로 a0 = 0, aN-1 = 1이다., N-1번째 분기점은 상대 넥서스이기 때문에 어쩔 수 없이 상대의 시야에 보이게 되며, 또 유일하게 상대 시야에 보이면서 갈 수 있는 곳이다.

다음 M개의 줄에 걸쳐 세 정수 a, b, t가 공백으로 구분되어 주어진다. (0 ≤ a, b < N, a ≠ b, 1 ≤ t ≤ 100,000) 이는 a번째 분기점과 b번째 분기점 사이를 지나는데 t만큼의 시간이 걸리는 것을 의미한다. 연결은 양방향이며, 한 분기점에서 다른 분기점으로 가는 간선은 최대 1개 존재한다.

 

출력

첫 번째 줄에 유섭이의 챔피언이 상대 넥서스까지 안 들키고 가는데 걸리는 최소 시간을 출력한다. 만약 상대 넥서스까지 갈 수 없으면 -1을 출력한다.

 

풀이

다익스트라를 이용해 0부터 N까지의 최소 경로를 구하는 문제이다! 여기에 추가로 적의 시야에 보이는지 여부만 판단하면 된다.

다익스트라는 시작 노드로부터의 누적 거리가 가장 짧은 노드를 우선적으로 방문하면서, 인접한 노드들의 최단 거리 정보를 갱신하는 최단 경로 알고리즘이다.

 

누적 거리(distance)가 가장 짧은 노드부터 방문하기 때문에 우선순위 큐(최소힙)를 사용한다.

 

heapq 라이브러리가 단순히 우선순위 큐를 구현한 것... 최소힙을 구현한 것...이라는 정도만 알고있어서 푸는 데 어려움이 있었는데, heapq에 대한 이해를 먼저 한 후 문제를 푸니 더 도움이 되었다.

 

 

heapq.heappush(q, (0, 0))

처음엔 이 코드가 잘 이해가 안되었는데, 이건 q에 (0, 0)을 push한다는 의미이다.

q는 우선순위 큐 역할을 하는 리스트로, 내부적으로 heapq는 리스트를 힙 구조처럼 다뤄서 사용한다.

 

또한

 

heapq.heappop(q)

이 코드는 q에서 최소힙의 조건을 만족하는, 가장 작은 원소를 꺼낸다는 의미이다. 위 전체 코드를 보면 q의 한 원소에는 거리와 이웃 노드가 튜플형태로 저장되는 것을 알 수 있는데, 이때 튜플에서 (거리, 노드)로 거리를 먼저 저장하기 때문에 거리를 기준으로 먼저 비교하여 거리가 가까운 노드를 먼저 pop한다.

 

코드 주석으로 이해하기!

import heapq

N, M = map(int, input().split()) # 엣지, 노드
visibility = list(map(int, input().split()))

INF = float("inf") # 혹은 int(1e9)
graph = [[] for _ in range(N)]
distance = [INF] * N

for _ in range(M):
    a, b, t = map(int, input().split()) # a <-> b의 가중치 t
    graph[a].append((b, t))
    graph[b].append((a, t)) # 양방향으로 저장

def dijkstra():
    q = []
    heapq.heappush(q, (0, 0))  # q에 (거리, 노드번호) 튜플 저장
    distance[0] = 0
    
    while q:
        dist, now = heapq.heappop(q)  # q에서 가장 dist가 작은 원소 pop
        
        if now == N - 1:
            return distance[now]
        if distance[now] < dist or visibility[now]:  # 기존 거리가 현재 거리보다 더 작거나 적의 시야에 들어오는 노드는 무시
            continue
        for neighbor, cost in graph[now]:
            new_cost = dist + cost
            if new_cost < distance[neighbor]:  # 기존 거리보다 새 거리가 더 작으면
                distance[neighbor] = new_cost  # 거리 갱신
                heapq.heappush(q, (new_cost, neighbor))  # q에 노드 추가

    return -1

print(dijkstra())