백준 1956번: 운동 (Python, PyPy3)

접근

처음에는 접근을 플로이드 와샬 알고리즘을 이용하여 모든 정점 사이의 이동 시간을 작성하고, i에서 j, j에서 i로 가는 이동 시간의 합들을 구하여 그 최소값을 표시하는 식으로 했더니 Python에서는 시간초과, PyPy3에서는 통과되었다.

플로이드 와샬 알고리즘 참고 문제: 2021.04.21 - [코딩/백준 (Python)] - 백준 11404번: 플로이드 (Python)

백준 11404번: 플로이드 (Python)

코드를 약간 수정하여, 기존 플로이드 와샬 알고리즘 3중 순환에서 i != j 조건을 빼주면 road[i][i] 에 제자리로 돌아오는 이동 경로가 갱신되게 된다. 이렇게 풀어도 비슷한 정도의 속도로 문제가 해결되고, 개선되지는 않는다.

코드

import sys

INF = float('inf')
v, e = map(int, sys.stdin.readline().split())
road = [[INF] * (v + 1) for _ in range(v + 1)]
for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    if road[a][b] > c:
        road[a][b] = c

for k in range(1, v + 1):
    for i in range(1, v + 1):
        for j in range(1, v + 1):
            if i != j and road[i][j] > road[i][k] + road[k][j]:
                road[i][j] = road[i][k] + road[k][j]

minimum = INF
for i in range(1, v):
    for j in range(i + 1, v + 1):
        minimum = min(minimum, road[i][j] + road[j][i])

# for k in range(1, v + 1):
#     for i in range(1, v + 1):
#         for j in range(1, v + 1):
#             if road[i][j] > road[i][k] + road[k][j]:
#                 road[i][j] = road[i][k] + road[k][j]
# 
# minimum = INF
# for i in range(1, v + 1):
#     minimum = min(minimum, road[i][i])

print(-1 if minimum == INF else minimum)

더 생각해 볼 것?

아무래도 1 -> 2 -> 3 -> 1 의 순환을 가지고 있을 때, 1 -> 2 / 2 -> 1 의 루트와 1 -> 3 / 3 -> 1의 루트가 동일하고, 이 중복을 피할 수 없기 때문에 시간적인 부족함이 생기는 것 같다. 하지만 아직 이 중복을 잡아낼 만한 아이디어가 떠오르지 않아 차후 한번 더 고민해 볼 여지가 있을 것 같다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!