알고리즘/플로이드 와샬 (Floyd Warshall)
-
[백준 11404] - [플로이드 와샬] - 플로이드 (JAVA)알고리즘/플로이드 와샬 (Floyd Warshall) 2018. 12. 28. 16:19
문제 링크 : https://www.acmicpc.net/problem/11404이 문제는 새로 접하는 알고리즘인 플로이드 와샬(Floyd Warshall) 알고리즘이다. 최단 경로를 구하는 알고리즘이다. 2차원 배열로 존재하면서 기준점 K를 두고 I에서 J 까지 가는 거리와 I에서 K 까지 갔다가 K에서 J 까지 가는 거리 두가지를 비교하여 최소 값을 최단 거리로 구하면 된다. 문제에서 주어진 예제 입력으로 플로이드 와샬 알고리즘을 공부해보자. 이 문제에서 요구하는 답은 N 개의 도시가 존재하고 1 부터 N까지의 도시각 각각의 도시에 갈 수 있는 최소 비용이다. N x N 의 2차원 배열로 존재하고 각 도시의 도달할 수 있는 최소비용이 저장되면 된다. 비용을 저장하는 배열에는 무한대의 값으로 초기화 해..