[백준] 11404 플로이드

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

초기에 특정 노드에서 다른 노드로 가는 최단 거리를 구하기 위하여 다익스트라를 이용하여 구하였습니다.

그러나 모든 노드에서 다른 노드로 이동하는 최단 거리를 구하여야 했기에, N개에 노드에 대해서 다익스트라를 N번 이용하여야 했습니다.

이로 인하여 시간 초과가 발생하였습니다.

 

모든 노드에서 다른 모든 노드로 이동하는 최단 거리를 한번에 구하기 위하여 '플로이드 워셜' 알고리즘을 이용하였습니다.

다익스트라와 플로이드 워셜 알고리즘의 용도에 대해 비교를 간단하게 해보자면, 다익스트라는 특정 노드에서 출발하여 다른 노드들로 향하는 최단 거리를 빠르게 구할 수 있다면, 플로이드 워셜 알고리즘은 모든 노드에서 다른 노드들로 향하는 최단 거리를 구할 수 있습니다.

또한 다익스트라는 음의 가중치의 간선에서 사용 할 수 없지만, 플로이드 워셜은 음의 가중치를 가진 경로가 있을 경우에도 사용이 가능합니다.

2) 알고리즘

• 플로이드 워셜

3) 풀이 코드

사용 언어 - Python

import sys

N = int(sys.stdin.readline())                                               # 노드의 개수
M = int(sys.stdin.readline())                                               # 간선의 개수
distance = [[1e10] * N for _ in range(N)]                                   # 노드간 최소 거리

for _ in range(M):                                                          # 간선들 정보
    start, end, weight = map(int, sys.stdin.readline().split())             # 노드간 거리 최소값 갱신
    distance[start-1][end-1] = min(distance[start-1][end-1], weight)

for k in range(N):
    distance[k][k] = 0                                                      # 본인 노드로 가는 거리는 0으로 할당
    for i in range(N):
        for j in range(N):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])       # 중간에 다른 노드를 거쳐서 가는 경우와, 바로 가는 경우 중 더 작은 값을 저장

for i in range(N):
    for j in range(N):
        if distance[i][j] == 1e10:          # 해당 노드로 이동 할 수 없는 경우 0으로 할당
            distance[i][j] = 0
    print(*distance[i])                     # 출력

---

🔗 문제 링크

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

11404번: 플로이드

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다