(JAVA) 백준 11404번 : 플로이드 --- [플로이드 - 와샬]

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

11404번: 플로이드

 

안녕하세요.

 

문제 이름을 들으면 알 수 있듯이

 

플로이드 - 와샬 알고리즘을 사용하는 기본 문제입니다.

 

 

플로이드 와샬 알고리즘에 대해서는 별도로 정리할 예정이지만,

 

정의만 간단하게 말하면 

 

모든 노드 -> 모든 노드 로 가는 최단 거리 를 2차원 배열로 정리하는 알고리즘입니다.

 

추가로, 거쳐가는 모든 경유 지점까지 고려해서 도출한 최단거리 라고 생각하시면 됩니다.

 

 

 

알고리즘 일부 코드를 보면

 

i , k, j 세 개의 index로 for문을 O(n^3) 돌리는데, 

 

i = 시작점

k = 경유지점

j = 도착점

으로, 시작점 -> 도착점 vs시작점 -> 경유지점 -> 도착점 을 통해 거리를 갱신합니다.

if(map[i][j] > map[i][k] + map[k][j]) {
	map[i][j] = map[i][k] + map[k][j];
}

  -  소스코드 중 일부

 

 

그래서 속도는 다른 알고리즘(다익스트라, 벨만-포드) 보다는 느리지만, 경유지점을 구해야 할 경우나 모든 지점 -> 모든 지점 의 최단 경로를 구하고 싶을 때 주로 사용합니다.

 

 

그렇기에, 이 문제는 플로이드 와샬 알고리즘을 사용하면 바로 해결하는 문제입니다.

 

 

이상입니다.

 

감사합니다!

 

 

 

 

소스코드

---