그래프 - 최단거리 알고리즘 1 다익스트라 알고리즘 문제2 - 소방차

문제 파악

최단 거리를 구하는 문제지만 특이한 조건들로 인해 간단히 접근할 수 없다. 먼저 정점들이 소방서, 불난 곳, 불나지 않은 곳으로 나뉘어져 있다. 불난 곳들과 소방서 사이의 최단 거리를 구해야 한다. 따라서 정점마다 가장 가까운 소방서가 다르고 이에 따라 다익스트라 알고리즘을 여러번 돌리는 과정이 필요하게 되어 시간 제한을 초과하게 된다.

문제 풀이

이 문제를 해결하는 핵심적인 아이디어는 각 소방서들을 모두 시작점으로 해서 다익스트라 알고리즘을 돌리는 것이다. 각 소방서들을 0의 가중치를 갖는 간선들로 연결하면 결과적으로 모든 소방서를 시작점으로 보는 것과 같은 정점 별 최단 거리를 구할 수 있게 된다. 불난 정점에선 어떤 소방서가 가장 가까운지는 알 필요가 없고 그 거리만 알면 되기 때문에 모든 소방서를 하나의 정점처럼 생각해도 되는 것이다.

느낀점

음의 가중치가 없는 무향 그래프에서 각 정점을 가중치가 0인 간선으로 연결하게 되면 그 정점은 같은 정점으로 생각해도 된다.