2 분 소요

1. 문제

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

// 예제 입력 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


2. 핵심 아이디어


3. Python 문제풀이

import heapq
import sys
input = sys.stdin.readline
INF = sys.maxsize

def dijkstra(start) :
  q = []
  heapq.heappush(q, (0, start))
  dist[start] = 0
  while q :
    d, now = heapq.heappop(q)
    if dist[now] < d :
      continue
    for v, w in graph[now] :
      cost = d + w
      if cost < dist[v] and ck[v] == 0 :
        dist[v] = cost
        heapq.heappush(q, (cost, v))

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
dist = [INF] * (n+1)
ck = list(map(int, input().split()))
ck[-1] = 0

for _ in range(m) :
  a, b, t = map(int, input().split())
  graph[a].append((b, t))
  graph[b].append((a, t))
  
dijkstra(0)
print(dist[n-1] if dist[n-1] != INF else -1)


4. Java 문제풀이


댓글남기기