배움과 성장/알고리즘·문제풀이
백준 1753 최단경로: Python heapq 다익스트라 풀이
백준 1753번 ‘최단경로’는 방향 그래프에서 시작 정점부터 모든 정점까지의 최단 거리를 구하는 문제다. 간선 가중치가 양수이므로 heapq를 이용한 다익스트라 알고리즘을 적용할 수 있다.이 문제에서 중요한 구현 포인트는 세 가지다.인접 행렬이 아니라 인접 리스트로 최대 300,000개의 간선을 저장한다.heap에는 (현재까지 거리, 정점) 순서로 넣어 가장 가까운 정점을 먼저 꺼낸다.같은 정점의 예전 거리도 heap에 남을 수 있으므로 stale entry를 건너뛴다.백준 1753번 문제문제를 그래프로 바꾸기입력은 u v w 형태의 방향 간선을 준다. 이는 정점 u에서 v로 이동하는 비용이 w라는 뜻이다. 반대 방향 간선은 별도로 주어졌을 때만 존재한다.시작 정점의 거리는 0, 나머지 정점의 거리는 아..