백준 1956번 운동

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

1956번: 운동

플로이드 알고리즘에서 그래프(D)의 대각선 요소(D[i][i])를 0으로 초기화시키지 않은 채(즉, 매우 큰 수로 둔 채) 3중 for문을 돌리면 이 대각선 요소에 저장되는 값은 무엇이 될까?

정답은 해당 지점(i)에서 다른 지점을 거쳐서 다시 해당 지점(i)으로 돌아오는 최소비용이 저장된다는 것이다.

 

강의에서 배운 알고리즘을 제대로 이해하고 코드를 작성한다고 생각하고 있었는데, 조금만 문제가 바뀌어서 나오면 힘들어진다. 백준 1956번(운동) 문제가 그랬다. 대표적인 플로이드 알고리즘 문제를 풀고 나서 다른 문제들도 이렇게 풀어야지 했는데 그게 아니었던 것이다. 1956번 문제는 대각선 요소를 0으로 초기화시키지 않을 때 훨씬 간결하게 코드 작성이 가능해진다. 아래 두 코드 중 첫번째 코드는 내가 작성한 코드, 아래의 두번째 코드는 함께 스터디를 하고 있는 분의 코드이다. 코드를 비교하면서 플로이드 알고리즘에 대해 더 잘 이해할 수 있었다.

# 백준 1956번 운동 
# 다익스트라(heapq)로 다시 풀어보기. Python3에서도 통과되는지 보기.

import sys
input = sys.stdin.readline

INF = int(1e9)
V, E = map(int, input().split())
D = [[INF]*(V+1) for _ in range(V+1)]

for _ in range(E):
    a, b, c = map(int, input().split())
    D[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 (D[i][k] + D[k][j] < D[i][j]):
                D[i][j] = D[i][k] + D[k][j]

result = INF
visited = []
for i in range(1, V+1):
    for j in range(i+1, V+1):
        if (i not in visited) and (j not in visited) and (D[i][j] != INF) and (D[j][i] != INF):
            if (result > D[i][j] + D[j][i]):
                result = D[i][j] + D[j][i]
                visited.extend([i,j])

if (result == INF):
    print(-1)
else:
    print(result)

# 백준 1956번 운동 (좀 더 나은 풀이법)
# 플로이드 알고리즘에서 그래프(D)의 대각선 요소를 0으로 초기화시키지 않은 채(매우 큰 수로 둔 채) 3중 for문을 돌리면
# 3중 for문을 돌고 나서 대각선 요소에 저장되는 값은 ?
# 해당 지점(i)에서 다른 지점 거쳐서 다시 해당 지점(i)로 돌아오는 최소 비용이 저장됨.

import sys
input = sys.stdin.readline

INF = int(1e9)
V, E = map(int, input().split())
D = [[INF]*(V+1) for _ in range(V+1)]

for _ in range(E):
    a, b, c = map(int, input().split())
    D[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 (D[i][k] + D[k][j] < D[i][j]):
                D[i][j] = D[i][k] + D[k][j]

result = INF
for i in range(1, V+1):
    result = min(result, D[i][i]) #위 코드와 다른 점

if (result == INF):
    print(-1)
else:
    print(result)