백준 1753 최단경로 파이썬 풀이

난이도 : 골드4

풀이일 : 2401162

https://www.acmicpc.net/problem/1753

1753번: 최단경로

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys, heapq


def dijkstra(n):
    visited[n] = 0
    queue = []
    heapq.heappush(queue, [visited[n], n])

    while queue:
        distance, now = heapq.heappop(queue)

        if distance <= visited[now]:
            for cost, next in load[now]:
                if visited[next] > distance + cost:
                    visited[next] = distance + cost
                    heapq.heappush(queue, [distance + cost, next])

    return



V, E = list(map(int, sys.stdin.readline().split()))
load = [[] for _ in range(V + 1)]
start = int(sys.stdin.readline())
INF = 10 * (V + 1)
visited = [INF for _ in range(V + 1)]

for i in range(E):
    s, e, w = list(map(int, sys.stdin.readline().split()))
    load[s].append([w, e])

dijkstra(start)

for i in range(1, V+1):
    print(visited[i] if visited[i] < INF else "INF")

heapq로 dijkstra 알고리즘 풀이

• visited : 출발지점부터의 최소 거리 기록을 위한 배열
• 입력받은 정보 load 2차원 그래프에 기록
• 가중치가 작은 경로부터 탐색하며 길이 있는 경우 visited 숫자 갱신
•  전체 visited에 대해 INF보다 작은 값일 경우 값 출력, 같은 값을 경우 INF 문자 출력

---

추가 오답 코드 - 시간초과

import sys
from collections import deque


def dijkstra(n):
    visited[n] = 0
    queue = deque()
    queue.append([visited[n], n])

    while queue:
        queue = deque(sorted(queue))
        distance, now = queue.popleft()

        if distance <= visited[now]:
            for cost, next in load[now]:
                if visited[next] > distance + cost:
                    visited[next] = distance + cost
                    queue.append([distance + cost, next])

    return


V, E = list(map(int, sys.stdin.readline().split()))
load = [[] for _ in range(V + 1)]
start = int(sys.stdin.readline())
INF = 10 * (V + 1)
visited = [INF for _ in range(V + 1)]

for i in range(E):
    s, e, w = list(map(int, sys.stdin.readline().split()))
    load[s].append([w, e])

for i in range(V + 1):
    load[i].sort()

dijkstra(start)

for i in range(1, V+1):
    print(visited[i] if visited[i] < INF else "INF")

heapq 안쓰고 어제 문제처럼 풀어보기 위해 deque로 풀이 시도

queue를 매번 정렬해줬는데, 시간 복잡도가 올라가서 시간초과가 나오게 된다.

쳇 안되네

---

느낀점

• 8달 전에 진짜 엄청 틀렸네 싶어서 웃겼다ㅋㅋㅋㅋㅋ
• 괜히 고집부리지 말고 뭔가 안되는 것 같으면 찾아보고 배워서 알고리즘 실력을 늘려야하는데 왜 이렇게 다른 사람 코드를 보고 공부하는게 싫을까? 내가 생각해내고 싶어서 시간만 오래걸리고 실력이 엄청 천천히 느는 것 같다.
• heapq에 넣을 때, distance + cost 말고 cost로 넣어서 한 번 틀렸다. 꼼꼼히 보고 문제를 풀자