[백준] 1753번 최단경로 - 파이썬(Python)

문제 (링크)

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

1753번: 최단경로

 

나의 풀이

import sys
import heapq

input = sys.stdin.readline
n, m = map(int, input().split())
start = int(input())
graph = [[] * (n+1) for _ in range(n+1)]
INF = int(1e9)
distance = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            current_cost = distance[now] + i[1]

            if current_cost < distance[i[0]]:
                distance[i[0]] = current_cost
                heapq.heappush(q, (current_cost, i[0]))

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == int(1e9):
        print("INF")
    
    else:
        print(distance[i])

 

접근법 및 코드설명

다익스트라 알고리즘을 직접적으로 사용해볼 수 있는 연습문제였다.

 

처음에는 우선순위큐를 사용하는게 아닌 매번 방문처리가 되지 않은 거리가 가장 작은 인덱스를 골라서 연산을 해주는 방식으로 구현하였으나, 시간초과 판정을 받았다.

 

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
start = int(input())
graph = [[] * (n+1) for _ in range(n+1)]
INF = int(1e9)
distance = [INF] * (n+1)
visited = [False] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def get_smallest_node():
    min_value = INF
    min_index = 0

    for i in range(n-1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            min_index = i

    return min_index


def dijkstra(start):
    distance[start] = 0
    visited[start] = True

    for i in graph[start]:
        distance[i[0]] = i[1]
    
    for i in range(n-1):
        now = get_smallest_node()
        visited[now] = True

        for i in graph[now]:
            current_cost = distance[now] + i[1]

            if current_cost < distance[i[0]]:
                distance[i[0]] = current_cost

dijkstra(start)
for i in range(1, n+1):
    if distance[i] == int(1e9):
        print("INF")
    
    else:
        print(distance[i])