감을 다시 찾아가기 (#1754 최단경로)

#1753 최단경로 https://www.acmicpc.net/problem/1753

 

import sys
import heapq

INF = sys.maxsize

n, e = map(int, input().split())

target = int(input())

# 0번 인덱스는 사용하지 않음. 1~n
maps = [[] for _ in range(n + 1)]
# visited = [[False] * (n + 1) for _ in range(n + 1)]

for i in range(e):
    start, end, weight = map(int, input().split())
    # 방향그래프
    maps[start].append((end, weight))

q = []
heapq.heappush(q, (0, target))
answer = [INF] * (n + 1)
while q:
    weight, prev = q.pop(0)
    if weight > answer[prev]:
        continue
    for end, w in maps[prev]:
        next_w = weight + w
        if next_w < answer[end]:
            # visited[prev][i] = True
            answer[end] = next_w
            heapq.heappush(q, (next_w, end))

for i in range(1, n + 1):
    if i == target:
        print(0)
    elif answer[i] < INF:
        print(answer[i])
    else:
        print("INF")

 

 

BFS로 풀었다.

 

세 가지 배움을 얻을 수 있었다.

 

1. 그래프를 저장할 때, 여러 방법이 있음을 기억하자.

인접 행렬, 인접리스트, 간선 리스트

이는 다음 블로그를 참고하자

https://velog.io/@eunchae2000/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84%EB%A5%BC-%EC%A0%80%EC%9E%A5%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95-3%EA%B0%80%EC%A7%80-%EC%9D%B8%EC%A0%91-%ED%96%89%EB%A0%AC-%EC%9D%B8%EC%A0%91-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EA%B0%84%EC%84%A0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-with-Python

[자료구조] 그래프를 저장하는 방법 3가지 : 인접 행렬, 인접 리스트, 간선 리스트 with Python

 

 

2. 힙큐를 써야 빠르다.

파이썬의 힙큐는 최소힙이라서, 가장 작은 값을 먼저 pop할 수 있다. 따라서 위와 같은 최단거리 문제를 풀 때 유용하다.

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

값을 저장할 때, set, list형태로 저장이 가능한데, (weight, node) 형태로 저장을 하면 제일 첫 번째 값인 weight를 기준으로 최소힙을 저장한다.

 

3. 최댓값을 작성할 때 sys.maxsize를 사용하자.

논리적으로 11이라고 생각하고 풀었었는데, 생각해보니 11보다 더 커지는 경우가 많다.

그냥 sys.maxsize 사용하자.