[백준 11404] 플로이드 - Java

이 문서는 [BOJ 11404 플로이드] 문제를 바탕으로 작성되었습니다. #BOJ #백준 #11404 #플로이드 #Java #Graph #FloydWarshall #플로이드워셜 #Dijkstra #다익스트라 #BitwiseOperation #비트연산 제목에 걸맞게 Floyd-Warshall 알고리즘으로 푸는 문제다.

플로이드에서는 기본 중의 기본인 문제라고 볼 수 있다. 거리 비용이 자연수라는 조건이 있기 때문에 Dijkstra 알고리즘 적용이 가능하다.

그러나 Dijkstra보다 Floyd로 푸는 게 더 빠른 문제다. 원인으로는 다음과 같다. a.

아마도 input이 희소그래프로 주어지지 않는 듯하다. b. A to B의 경로가 여러 개 주어질 수 있다.

이 경우 ArrayList로 만든 graph의 경우 무의미한 반복을 초래한..........