[BOJ] [Python] 1753번 : 최단경로

처음에는 2차원 배열을 이용해서 푸려는 무모한 계획을 세웠다.

 

이 문제에서 2차원 배열을 이용하려면, 최대 20000 x 20000[400,000,000]이 필요하다.

파이썬은 300,000,000부터 메모리 초과가 난다. 100,000,000에 381MB이다.

 

이 문제는 메모리가 256MB 제한이라서 300,000,000보다 작아도 메모리 초과이다.

 

 

 

그래서 2차원 배열 대신 heapq를 이용하여 풀었다.

heapq를 사용한 이유는 최단 거리에 있는 노드를 선택하기 위함이다.

 

아래 예시로 설명해보면, 4로 가는 최단 거리에 있는 노드는 3이다. 

heapq가 없었다면, 2->4부터 계산하고 그다음에 3->4를 계산할 것이다.

그렇게 되면 4는 2번이나 이전보다 짧은 최단 거리를 만들었기 때문에, 4가 순서 리스트에 2번 들어가게 된다.

하지만 우선순위를 2보다 3을 더 높게 한다면, 3->4를 먼저 계산한다.

그다음, 2->4를 계산하면 이전보다 더 먼 거리이기 때문에, 4를 순서 리스트에 넣지 않게 되어 최종적으로 4는 1번만 들어가게 된다.

 

 

입력 예제

 

5 6

1

5 1 1

1 2 3

1 3 2

2 3 4

2 4 6

3 4 6

 

예제 입력1 응용

 

 

# 정점의 개수 : V (1 ~ V)
# 간선의 개수 : E
# 시작 정점 : K

# u, v, w (u -> v 가중치)
#  서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.


import sys
import heapq

input = sys.stdin.readline

v, e = map(int, input().split())
k = int(input())

val = [int(1e9)] * (v + 1)  # 값
val[k] = 0 # 시작 지점 초기화

order = [] # 순서
heapq.heappush(order, (0, k)) # (거리, 위치)

route = [] # 경로

for _ in range(v + 1):
    route.append([])

for _ in range(e):
    num = list(map(int, input().split()))
    route[num[0]].append((num[1], num[2])) # (목적지, 가중치)

while order:

    dist, now = heapq.heappop(order)

    for i, weight in route[now]:

        cal = val[now] + weight

        if cal < val[i]:
            val[i] = cal

            heapq.heappush(order, (cal, i))


for result in val[1:]:
    if result == int(1e9):
        print("INF")
    else:
        print(result)

 

 

 

 

아래는 처음에 2차원 배열을 이용해서 푼 풀이이다.

 

# 정점의 개수 : V (1 ~ V)
# 간선의 개수 : E
# 시작 정점 : K

# u, v, w (u -> v 가중치)
#  서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

# 경로 : []
# 값 : [x, 0, 무한, 무한, 무한]

import sys

input = sys.stdin.readline

v, e = map(int, input().split())
k = int(input())

route = [] # 경로
weight = [[int(1e9)] * (v + 1) for col in range(v + 1)] # 가중치
# weight = [[int(1e9)] * (v + 1)] * (v + 1)

# print(weight)

val = [int(1e9)] * (v + 1)  # 값
val[k] = 0

for _ in range(v + 1):
    route.append([])

for _ in range(e):

    num = list(map(int, input().split()))
    store = weight[num[0]][num[1]]

    route[num[0]].append(num[1])

    if num[2] < store:
        weight[num[0]][num[1]] = num[2]

order = [k]  # 순서 리스트

while order:

    now = order[0]

    for i in route[now]:

        cal = val[now] + weight[now][i]

        if cal < val[i]:
            val[i] = cal

            order.append(i)

    order.pop(0)

# print(weight)
for result in val[1:]:
    if result == int(1e9):
        print("INF")
    else:
        print(result)