floydwarshall

floydwarshall

    백준 1507 / 플로이드 와셜(Floyd Warshall) 알고리즘 / JAVA

    이번에 살펴볼 문제는 백준 1507번 궁금한 민호 문제이다. https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 이 문제는 플로이드 와셜 알고리즘을 통해 모든 경로를 탐색하여 푸는 문제이다. 모든 쌍의 최단 경로를 다 확인하는 문제로 이 알고리즘이 익숙하지 않으면 조금 생각하기 어려울 수도 있다. 먼저 플로이드 와셜 알고리즘에 대해 간단하게 설명한 후에 문제를 풀어 보도록 하겠다. 플로이드 와셜 알고리즘(Floyd Warshall Algorit..