백준 11404 Java

문제

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

알고리즘 설명

플로이드 워셜 의 개념 문제이다.

N*M 의 시간 복잡도를 도시 개수 만큼 연산되기 때문에 N3제곱 의 시간복잡도가 걸린다.

최초에 각각 도시에 갈 수 있는 비용으로 배열을 만든 후

기준점 K (도시 번호)를 두고
I --> J 까지 가는 거리와 I-->K 로 갔다가 K--> J 로 가는 거리를 비교하면서
풀탐색을 하면 된다.

Math.min ( DP[I][J], DP[I][K] + DP[K][J])

구현코드

구현 코드는 깃 허브로 옮겼다.

https://github.com/melong222/SW/blob/master/SW/src/BACKJOON/B11404.java