[Python] 백준 - 1753번 최단경로(1)

문제

• 백준 1753번

최종 코드

import sys
import math
from collections import deque
input = sys.stdin.readline

V, E = map(int, input().split())
visited = [False] * (V + 1)
distance = [math.inf] * (V + 1)
g = [[] for _ in range(V + 1)]

k = int(input())
distance[k] = 0

for _ in range(E):
    u, v, w = map(int, input().split())
    g[u].append((v, w))


def find_min_distance_node():
    min_distance = math.inf
    node_num = -1
    for i in range(1, V + 1):
        if distance[i] < min_distance and not visited[i]:
            min_distance = distance[i]
            node_num = i

    return node_num


que = deque()
que.append(k)

while que:
    now = que.popleft()
    visited[now] = True

    for t in g[now]:
        node, value = t[0], t[1]
        distance[node] = min(distance[node], distance[now] + value)

    next = find_min_distance_node()
    if next != -1:
        que.append(next)

for i in range(1, V + 1):
    if distance[i] == math.inf:
        print("INF")
        continue

    print(distance[i])

 

풀이 과정

---

• 문제에서 방향 그래프가 입력으로 주어지고 시작 노드로부터 다른 모든 노드로의 최단 경로를 구하는 문제이다
• 해당 문제에서 주어지는 그래프의 가중치는 10 이하의 자연수이므로 그래프에서 최단 거리를 구하는 알고리즘 중 다익스트라 알고리즘으로 해당 문제를 풀어보기로 했다!
• 처음에는 다익스트라 알고리즘을 학습 했던대로 방문 리스트와 최단 거리 리스트를 이용하였다
• 최단 거리 리스트 중 최솟값을 가지는 노드를 선택해 해당 노드와 연결된 에지의 가중치를 이용하여 최단 거리 리스트를 업데이트하는 것을 반복하도록 구현하였다!
  • find_min_distance_node() 함수를 통해 선택하지 않은 노드 중 최단 거리 리스트에서 최솟값을 가지는 노드를 반환하였고, 해당하는 노드가 없으면 -1을 반환하였다
• 하지만 해당 코드를 제출했을 때, 처음에는 시간초과(Time out)이었고 다시 제출했을 때 통과했다...
• 확실히 반복문을 돌며 최단 거리 리스트에서 최솟값을 가지는 노드를 찾다보니 시간이 오래 걸린 것 같다는 생각이 들어 어떻게하면 시간을 더 줄일 수 있을지 고민해봐야겠다
  
  • 다음에 계속...
  • 실행 시간을 줄인 코드가 궁금하다면 아래 글로!

[Python] 백준 - 1753 최단경로(2)

[Python] 백준 - 1753 최단경로(2)

 

틀린 부분 또는 궁금한 점은 댓글로 남겨주세요! 항상 환영합니다!