[Python] 백준 1753번_최단경로

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

1753번: 최단경로

 

• 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로 구하기
• 단, 모든 간선의 가중치는 10 이하의 자연수

• 입력
  • 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어짐 (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)
    • 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정
  • 둘째 줄에는 시작 정점의 번호 K (1 ≤ K ≤ V)가 주어짐
  • 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어짐
    • u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻
    • u와 v는 서로 다르며 w는 10 이하의 자연수
  • 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의
• 출력
  • 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력
  • 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력
• 시간 제한: 1초
• 메모리 제한: 256 MB

 

"""
입출력 예시)

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

    -> 0
       2
       3
       7
       INF
"""

 

 

## 의사코드 ##

# 주어진 시작점에서 다른 모든 정점으로의 최단 경로 -> 다익스트라
# -> heapq로 구현

# 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리 저장
#     첫 정점의 거리는 0, 나머지는 무한대
# -> distances = {node: float('inf') for node in graph}
# -> distances[start] = 0

# 우선순위 큐에 [거리, 첫 정점] 저장
# -> q = []
# -> heapq.heappush(q, [distances[start], start])

# while q:
#     # 우선순위 큐에서 최소 거리를 가진 노드를 pop
#     현재 거리, 현재 노드 = heapq.heappop(q)
#     # 배열에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리를 가진 경우, 해당 노드와 인접한 노드간의 거리 계산을 하지 않고 skip 
#     if distances[현재 노드] < 현재 거리:
#         continue
#     # 주어진 시작점에서 해당 노드로 가는 거리 비교
#     for adj, weight in graph[현재 노드].items():
#         distance = 현재 거리 + weight
#         # 배열에 저장되어 있는 거리보다 주어진 시작점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트
#         if distance < distances[adj]:
#             # 최단 거리로 업데이트
#             distances[adj] = distance
#             # 우선순위 큐에 삽입
#             heapq.heappush(q, [distance, adj])

# for i in range(1, V+1):
#     # 경로가 존재하지 않는 경우 INF 출력
#     if distances[i] == float('inf'):
#         distances[i] = 'INF'
#     print(distances[i])

 

 

 

첫 번째 시도

 

import sys 
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())
k = int(input()) # 시작 정점의 번호(start)

# 그래프에 값 입력
graph = {}
for i in range(E):
    u, v, w = map(int, input().split())
    graph[u].append([v, w]) # [노드, 가중치]

# 시작 정점에서 각 정점까지의 거리 초기화 (무한대)
distances = {node:float('inf') for node in graph}
# 시작 정점의 거리는 0
distances[k] = 0

# 우선순위 큐에 [거리, 시작 정점] 저장
q = []
heapq.heappush(q, [distances[k], k])

while q:
    current_distance, current_node = heapq.heappop(q)
    if distances[current_node] < current_distance:
        continue 
    for adj, weight in graph[current_node].items():
        distance = current_distance + weight
        if distance < distances[adj]:
            distances[adj] = distance
            heapq.heappush(q, [distance, adj])

for i in range(1, V+1):
    if distances[i] == float('inf'):
        distances[i] = 'INF'
    print(distances[i], end=' ')

-> 런타임 에러

for문으로 출력하는 거니까 end=' '할 필요 없음

 

 

 

통과한 코드

 

import sys 
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())
k = int(input()) # 시작 정점의 번호(start)

# 그래프에 값 입력
graph = [[] for i in range(V+1)]
for i in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w)) # [노드, 가중치]

# 시작 정점에서 각 정점까지의 거리 초기화 (무한대)
distances = [float('inf')] * (V+1)
# 시작 정점의 거리는 0
distances[k] = 0

# 우선순위 큐에 [거리, 시작 정점] 저장
q = []
heapq.heappush(q, (distances[k], k))

while q:
    # 우선순위 큐에서 최소 거리를 가진 노드를 pop
    current_distance, current_node = heapq.heappop(q)
    # distances에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리를 가진 경우, 해당 노드와 인접한 노드간의 거리 계산을 하지 않고 skip 
    if distances[current_node] < current_distance:
        continue 
    # 주어진 시작점에서 해당 노드로 가는 거리 비교
    for adj, weight in graph[current_node]:
        distance = current_distance + weight
        # distances에 저장되어 있는 거리보다 주어진 시작점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트
        if distance < distances[adj]:
            # 최단 거리로 업데이트
            distances[adj] = distance
            # 우선순위 큐에 삽입
            heapq.heappush(q, (distance, adj))

for i in range(1, V+1):
    # 경로가 존재하지 않는 경우 INF 출력
    if distances[i] == float('inf'):
        distances[i] = 'INF'
    print(distances[i])

-> graph와 distances를 길이가 정해진 리스트로 구현

-> 튜플로 삽입: 메모리 68224 KB / 시간: 700 ms

 

• cf) 배열에 튜플이 아닌 리스트로 삽입하는 경우
  • -> 리스트로 삽입: 메모리 73388 KB / 시간: 912 ms
  • => 튜플이 더 빠름

 

• graph 입력 예시 

# graph 입력 예시 
V = 5
graph = [[] for i in range(V+1)]

graph[5].append((1, 1))
graph[1].append((2, 2))
graph[1].append((3, 3))
graph[2].append((3, 4))

print('graph:', graph)
print('graph[5]:', graph[5])

"""
graph: [[], [(2, 2), (3, 3)], [(3, 4)], [], [], [(1, 1)]]
graph[5]: [(1, 1)]
"""

 

 

 

다른 풀이

 

import sys
input = sys.stdin.readline
import heapq 
INF = int(1e9) # 무한대의 값으로 10억 설정

def dijkstra():
    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]:
            cost = dist + i[1]
            # 현재 노드를 거쳐 다른 노드로 가는 거리가 더 짧다면
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

# 노드의 개수, 간선의 개수
n, m = map(int, input().split())
# 시작 노드
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)

# 모든 간선 정보 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c
    graph[a].append((b, c))

# 다익스트라 알고리즘 수행
dijkstra()

# 각 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
    if distance[i] == 1e9:
        print('INF')
    else:
        print(distance[i])