백준_11404 플로이드

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

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

n = int(input())
m = int(input())
fee = [[float('inf')]*n for _ in range(n)] 

#fee 테이블 입력값 받기
for i in range(0, m):
    temp = input().split(' ')
    c = int(temp[0])-1
    l = int(temp[1])-1
    w = int(temp[2])

    if (fee[c][l] == 0):
        fee[c][l] = w
    elif (fee[c][l] > w): 
        fee[c][l] = w

# 왜 얘 주석처리하면 틀리는거임?? 
for i in range(n):
    fee[i][i] = 0

#fee 테이블 최소 비용 계산
for k in range(0, n):
    for i in range(0, n):
        for j in range(0, n):
            if (fee[i][j] > fee[i][k] + fee[k][j]): #fee[i][i]를 0으로 안해주면 여기에서 걸려서 새 값이 갱신됨
                fee[i][j] = fee[i][k] + fee[k][j]

for i in range(0, n):
    for j in range(0, n):
        if (fee[i][j] == float('inf')): // 여기까지 왔을 때 inf인 경우는 아예 그 도시로 가는 경로가 없는 경우임. 이 때는 0으로 설정
            fee[i][j] = 0
    
        print(fee[i][j], end = ' ')
    print('\n', end='')    

fee[i][i] = 0 으로 설정해주지 않으면 if (fee[i][j] > fee[i][k] + fee[k][j]): 에서 값이 걸려서 fee[i][k] + fee[k][j] 로 바뀐다


예를 들어서, fee[3][3]의 경우에는 정점 3에서 3으로 이동하는 것이기 때문에 비용은 당연히 0이다(같은 정점끼리 거리는 0이니까...)

그런데 0으로 초기화해주지 않으면 fee[i][j] > fee[i][k] + fee[k][j] 에서 fee[i][j]가 0이 아니니까 부등호가 true가 되는 경우가 발생한다 이 때 fee[i][j] 값이 0이 이닌 다른 값으로 설정되므로 오류가 발생한다