[백준/11404] 플로이드

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

11404번: 플로이드

---

 플로이드-워셜 알고리즘을 이용한 최단경로 문제는 나오기만 하면 정말 땡큐인 문제인 듯합니다. 이 문제 역시 그래프의 노드 개수가 100개 이하이므로, 플로이드-워셜 알고리즘을 사용하여 손쉽게 해결할 수 있습니다. 플로이드-워셜 알고리즘에 대한 조금 더 상세한 설명은 다음 링크를 참조바랍니다.

 

링크: https://jcy1996.tistory.com/24?category=958980 

플로이드-워셜 알고리즘

소스코드는 다음과 같습니다.

---

코드

n = int(input())
m = int(input())
array = []
for _ in range(m):
    array.append(input())

INF = int(1e5 + 1)

graph = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    graph[i][i] = 0
    
for row in array:
    s, e, d = list(map(int, row.split()))
    graph[s][e] = min(graph[s][e], d)
    
for k in range(1, n + 1):
    for i in range(1, n + 1):
        if i == k:
            continue
        for j in range(1, n + 1):
            if j == k:
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] != INF:
            print(graph[i][j], end=' ')
        else:
            print(0, end=' ')
    print()

---

풀이

 입력을 받아온 뒤에 그래프를 초기화해줍니다. 문제에서 도착할 수 없는 도시에 대해서 0을 출력하라고 하긴 했으나, 그렇다고 해서 그래프를 0으로 초기화하는 것은 좋지 못한 생각입니다. 최소값을 구해야 하는데 이미 0은 최소의 거리이기 때문입니다. 따라서 그래프를 INF(infinity)로 초기화하되 INF의 값은 비용이 최대 100,000이라는 것을 고려하여 100,001로 주겠습니다.

INF = int(1e5 + 1)

graph = [[INF] * (n + 1) for _ in range(n + 1)]

 또한 출발도시와 도착도시가 같은 경우 거리는 0으로 초기화해줍니다.

for i in range(n + 1):
    graph[i][i] = 0

 중요한 것은 문제 조건 중 '시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다'는 점입니다. 이말은 즉 비용은 다르지만 시작지점과 도착지점이 같은 간선이 존재할 수 있다는 말입니다. 따라서 입력받은 것을 그래프에 옮기는 것이 아니라, 최소값을 고려하여 가져와야 합니다.

for row in array:
    s, e, d = list(map(int, row.split()))
    graph[s][e] = min(graph[s][e], d)

 그 후 플로이드-워셜 알고리즘을 수행합니다.

for k in range(1, n + 1):
    for i in range(1, n + 1):
        if i == k:
            continue
        for j in range(1, n + 1):
            if j == k:
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

 혹시 업데이트되지 않은 지점이 남아있다면 그래프의 값이 INF로 남아있을 것입니다. 도착할 수 없는 지점에 대해서는 0을 출력하라고 문제에서 명시했으므로, 출력값이 INF인 경우 대신 0을 출력하도록 조건을 분기해주면 적절한 답을 얻을 수 있습니다.

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] != INF:
            print(graph[i][j], end=' ')
        else:
            print(0, end=' ')
    print()