BOJ 1507 궁금한 민호
-
백준 1507 궁금한 민호Algorithm/BOJ 2020. 6. 18. 13:33
출처: www.acmicpc.net/problem/1507 분류: Greedy, Floyd Wharshall 접근방식 플로이드 와샬 알고리즘을 사용했습니다. 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최소 비용을 구하는 알고리즘입니다. 이 문제는 그 결과가 주어진 경우라고 할 수 있는데요, 주어진 간선 중에서 가중치가 가장 작은 것부터 연결해가면서 플로이드 와샬로 다시 가중치 그래프를 완성시켜 나갑니다. 연결하려고 하는 간선의 가중치가 만들고 있는 가중치 그래프와 같다면 이미 다른 경로를 통해 연결이 되어 있으므로 연결하지 않습니다. 작은 경우에만 새로 연결합니다. 불가능한 경우에는 -1을 출력하라고 했으니, 복귀를 다 마친 다음에 원본과 다르다면 -1을 출력해줍니다. 해결방법 let n =..