[BOJ/Python] 17396_백도어

문제 출처:https://www.acmicpc.net/problem/17396

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을 출력한다.

예제 입력 1

5 7
0 0 0 1 1
0 1 7
0 2 2
1 2 4
1 3 3
1 4 6
2 3 2
3 4 1

예제 출력 1

12

위 그래프의 최단거리는 0-2-3-4 를 지나는 시간인 5(2+2+1) 이지만, 3번 분기점이 상대의 시야에 있기 때문에 0-2-1-4를 지나는 시간인 12(2+4+6)이 최소 시간이 된다.

 

예제 입력 2

5 7
0 1 0 1 1
0 1 7
0 2 2
1 2 4
1 3 3
1 4 6
2 3 2
3 4 1

예제 출력 2

-1

---

풀이

 

문제를 요약해 보면 다음과 같다.

1. 총 N개의 노드가 존재한다.
2. 0번 노드에서 n-1번 노드까지 최단거리로 이동해야 한다.
3. 이때, 각 노드에는 상태가 존재하는데 0일 경우, 이동이 가능하지만, 1일 경우 이동이 불가능하다.(n-1번 노드는 1이지만 이동이 가능하다.)
4. 최단거리를 구할 수 있다면 최단거리를 출력하고, 아니라면 -1을 출력하는 문제이다.

코드는 다음과 같다.

 

import sys
import heapq
 
INF = int(1e12)
 
def dijkstra():
    queue = []
    distance[0] = 0
    heapq.heappush(queue,(0,0))
 
    while queue:
        dist, node = heapq.heappop(queue)
 
        if node == n-1:
            return dist
 
        if distance[node] < dist:
            continue
 
        for next in graph[node]:
            if ward[next[0]]==0:
                cost = next[1] + dist
                if distance[next[0]] > cost:
                    distance[next[0]] = cost
                    heapq.heappush(queue,(cost,next[0]))
    return -1
 
 
n,m = map(int,sys.stdin.readline().split())
ward = list(map(int,sys.stdin.readline().split()))
ward[-1]=0
 
graph = [[] for _ in range(n)]
distance = [INF for _ in range(n)]
 
for _ in range(m):
    a,b,t = map(int,sys.stdin.readline().split())
    graph[a].append((b,t))
    graph[b].append((a,t))
 
print(dijkstra())

1. ward의 경우 각 노드의 상태를 의미한다. (1일 경우 이동이 불가능하고, 0일 경우 이동이 가능하다.)
2. n-1번 노드의 경우, ward가 1이지만, 편의상 0으로 바꾸어 이동이 가능하도록 하였다.
3. 이후는 다익스트라 알고리즘을 이용하여 최단거리를 구한다.
4. 만약 현재 노드와 연결되어 있는 다음 노드의 ward가 1이라면, 이동이 불가능하다.
5. 다음 노드의 ward가 0인 경우에만 최단거리를 구하며, 최종적으로 n-1번 노드에 도달하면 그 최단거리를 return 한다.
6. 만약 큐에 더 이상 원소가 없는데(더 이상 최단거리를 구할 노드가 존재하지 않는 상태), n-1번 노드에 도달하지 못했다면 -1을 return 한다.
7. 최종적으로 return 받은 값을 출력한다.