99클럽 코테 스터디 5기 8일차 TIL + 다익스트라

- 오늘의 학습 키워드

Dijkstra(최단경로, 다익스트라)

- 공부한 내용 본인의 언어로 정리하기

# https://www.acmicpc.net/problem/1504
import sys,heapq
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start) :
    distance = [INF] * n
    distance[start] = 0
    pq = []
    pq.append((distance[start],start))
    
    while pq :
        near_dist,near_node = heapq.heappop(pq)
        
        if near_dist > distance[near_node] :
            continue
        
        for i in arr[near_node] :
            dist = i[1] + near_dist 
            if dist < distance[i[0]] :
                distance[i[0]] = dist
                heapq.heappush(pq,(distance[i[0]],i[0]))
                
    return distance

n,e = map(int,input().split())
arr = [[] for _ in range(n)]

for _ in range(e) :
    a,b,c = map(int,input().split())
    arr[a-1].append((b-1,c))
    arr[b-1].append((a-1,c))
    
v1,v2 = map(int,input().split())
v1 -= 1
v2 -= 1

shortest_path = dijkstra(0)
move_to_v1 = dijkstra(v1)
move_to_v2 = dijkstra(v2)

path_1 = shortest_path[v1] + move_to_v1[v2] + move_to_v2[n-1]
path_2 = shortest_path[v2] + move_to_v2[v1] + move_to_v1[n-1]

result = min(path_1, path_2)

if result >= INF:
    print(-1)
else:
    print(result)
    
# 65152	408

- 오늘의 회고

1. 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 단순히 다익스트라를 사용해서 최단 경로를 구하면 되는 줄 알았지만 정점 v1과 v2를 반드시 지나야 하는 조건이 있었습니다.  우선 원점에서의 다익스트라를 구한 후, v1 까지의 경로와 v1에서 v2까지 가는 경로를 구한다음(distance[v2] - distance[v1]) 마지막으로 v2에서의 다익스트라로 최종경로로 가는 최단 거리를 구한다음 더 해주려고 했습니다.

2. 어떻게 해결했는지

case1 : 0 → v1 →v2 →n

case 2 : 0 → v2 → v1 → n

두 가지 케이스를 모두 생각해야 되는 문제였습니다.

3. 무엇을 새롭게 알았는지

최단 경로에서 조건이 주어졌을때 생각하는 방법?