<aside> 🔥 교재 이코테 문제

</aside>

<aside> 🔥 문제 정리

첫째줄에 n : 노드의 개수, k : 간선의 개수가 주어진다.

둘째줄에 s : 출발 노드 번호가 주어진다.

k개의 줄에 a : 시작점, b : 도착점, c : 걸리는 시간이 띄어쓰기로 주어진다.

각 노드에 가는 최단 경로를 출력하라.

예시

// 입력값
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

// 출력값
0
2
3
1
2
4

</aside>

<aside> 🔥 접근 방법

다익스트라 우선순위 큐 방법으로 진행해보았다.

기본적인 각각의 최소시간을 구하는 문제로 기본코드로 작성할 수 있었다.

</aside>

<aside> 🔥 코드 진행

1. 각각의 입력값을 txt파일로 분리해 불러오는 방식으로 작성했으며,

   그래프를 생성했다. 그래프는 일차원 그래프로 인덱스로 노드의 번호를 가리키고,

   각 인덱스 안에 간선으로 연결된 노드의 번호와 걸리는 시간을 튜플형태로 저장했다.

   with open('../test_case1.txt') as f:
       sys.stdin = f
       input = sys.stdin.readline
       n, k = map(int, input().split())
       s = int(input())
       graph = [[] for _ in range(n + 1)]
       for _ in range(k):
           a, b, c = map(int, input().split())
           graph[a].append((b, c))
   

2. 다익스트라 알고리즘을 사용하여 함수를 만들었다.

   파라미터로 그래프와 시작지점을 입력받는다.

   거리를 모두 무한대로 지정하고 시작한다.

   def dijkstra_pq(graph, start):
       N = len(graph)
       INF = int(1e9)
       dist = [INF] * N
   

3. 힙큐를 사용해서 시간복잡도를 줄였다. 힙에 튜플형태로 저장시 앞자리 기준으로 정렬이 되므로,

   (거리, 노드번호) 로 저장하도록 한다.

   다음으로는 최초 시작 노드의 거리를 0으로 바꾸어준다.

   q = []
       heapq.heappush(q, (0, start))
       dist[start] = 0
   

4. heap이 있는동안 반복한다.

   heap에서 값을 꺼내 누적된 거리, 현재 노드를 가져온다.

   현재 확인된값이 누적된 거리의 값보다 작을 경우 어차피 더 오래걸리므로 건너뛴다.

   사실 dist에 무한대가 아닌 값이 있단말은 이미 방문했으므로 건너뛴다는 것과 같다.

   acc, cur = heapq.heappop(q)
           # 현재 확인값의 거리가 누적보다 작으면
           # 어차피 더 느리니깐 건너뜀.
           if dist[cur] < acc:
               continue
   

5. 현재 노드의 인접노드를 방문한다.

   누적거리를 계산하고 누적거리가 기록되어있는것보다 빠를 경우에 업데이트 처리를해준다.

   for adj, d in graph[cur]:
               cost = acc + d  # 인접노드로 방문할떄 누적 거리
               if cost < dist[adj]:  # 누적거리가 기록되어있는거보다 더 빠를경우
                   dist[adj] = cost
                   heapq.heappush(q, (cost, adj))
   

</aside>