BOJ 1507 궁금한 민호

N개의 도시 사이의 최단 거리가 주어질  때, 주어진 정보를 만족하고 N개의 도시를 연결하는 도로의 개수를 최소로 하는 문제이다. 그리고 그 도로의 거리 값의 합을 구해야 한다.

어떻게 풀어야 할까?
백준님의 풀이를 봤다.

플로이드 와샬 알고리즘을 이용할 때,
a->b 거리와 b->c거리의 합이 a->c거리보다 작으면 갱신해주는 식으로 나가는 것 처럼
지금 주어진 정보는 각 도시사이의 최단거리이기 인데 주어진 대로 각 도시 사이의 길이 다 존재한다고 가정하고, 그 길에서 불필요한 길을 제거하는 식으로 풀어나갈 것이다.
예를 들면, (a->b + b->c)  >= (a->c) 가 될 것이다. 도로의 개수를 최소로 하려면
(a->b + b->c) == (a->c)인 경우에 a->c는 없어도 최단거리를 만족하므로 제거한다.
이런 식으로 나타낼 수 있는 길들을 제거해 나가면 된다.

그리고 만약 (a->b + b->c) < (a->c) 라면 최단거리가 주어졌다는 조건에 모순이므로...불가능한 경우이다!

그리고 주의해야 할 점이 x에서 x로 가는 거리는 0이므로 즉, 자기 자신에서 자기자신으로 가는 거리는 0이기 때문에 이 경우는 빼고 계산해야 한다. 그렇지 않으면 모든 길이 다 제거될 것이다. 그리고 내 예전 코드에서는 길이 제거되지 않은 경우에만 계산에 넣는데, 제거 되더라도 그 거리는 여전히 존재하는 것이므로 제거된 경우에도 계산을 하는게 맞는 것 같다. 오히려 길이 제거된 경우를 계산에서 빼버리면 안될 것 같은데... 공부를 좀 더 해봐야겠다.

플로이드 와샬뿐 아니라 그래프 알고리즘을 다시 공부해야 겠다. 벌써 기억이 잘 안난다. 끊임없이 공부하자!

출처 및 참고 : 백준님 강의 자료 및 풀이