[알고스팟] FIRETRUCKS - 소방차 (C++, 다익스트라)

문제

 

https://algospot.com/judge/problem/read/FIRETRUCKS

algospot.com :: FIRETRUCKS

 

풀이

 

종만북 난이도: 중

 

 

처음 문제를 접하면 여러 소방서들에서 불이난 곳으로의 최단 거리를 구해야 된다고 생각하게 됩니다.

하지만 단일 시작점 알고리즘인 다익스트라 최단 경로 알고리즘으로 모든 소방서로부터 불난 곳의 최단 거리를 구하는 것은 시간 초과를 발생시킵니다.

 

다익스트라 알고리즘의 복잡도는 간선(edge)의 개수를 E라고 할때 O(E logE) 이기 때문에

모든 테스트 케이스를 통과하지 못하고 시간 초과가 발생합니다.

 

따라서 두 가지 최적화를 진행하였습니다.

다익스트라 최단 경로를 구하는 함수 Dijkstra(int start_station)은 start_station에서 부터 각 정점으로의 최단 거리를 구합니다.

이를 dist[place_idx] = start_station에서부터 place_idx까지의 최단 거리로 저장합니다.

 

 

1. 모든 다익스트라 함수가 같은 dist 배열을 공유.

dist를 공유한다면 이미 다른 start_station에서의 최단 거리가 계산되어 있더라도

이번 출발 점으로 부터의 거리가 더 짧다면 dist는 새로운 값으로 갱신됩니다.

따라서 모든 소방서로부터 다익스트라를 실행시켜주면 모든 소방서들로부터 각 장소들로의 가장 짧은 거리를 구할 수 있습니다.

 

 

2. 다음 장소가 소방서라면 해당 정점으로의 탐색을 중단.

만약 다른 소방서(u)를 지나야 다른 정점(v)으로의 최단 거리를 구할 수 있다면,

해당 소방서(u)에서부터 해당 정점(v)으로의 최단 거리를 구하는 것이 더 짧을 수밖에 없습니다.

(모든 도로는 1분 이상의 시간이 걸리므로)

따라서 다음 인접 정점이 소방서라면 해당 정점으로의 탐색은 불필요합니다.

 

 

이러한 다익스트라 진행으로 최단 거리(dist)의 변화를 그림으로 나타내면 다음과 같습니다.

 

Dijkstra(4) 호출

 

Dijkstra(6) 호출

 

 

 

 

void Dijkstra(int start_station){
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  pq.push({0,start_station});
  dist[start_station] = 0;
  
  int now_place, cost, next_place, next_cost;
  while(!pq.empty()){
    now_place = pq.top().second;
    cost = pq.top().first;
    pq.pop();
 
    if(dist[now_place] < cost) 
      continue;
 
    for(int i=0; i<adj[now_place].size() ; ++i){
      next_place = adj[now_place][i].second;
 
      if(is_station[next_place])  //다음 장소가 소방소라면 더 이상 탐색 x 
        continue;
 
      next_cost = cost + adj[now_place][i].first;
 
      if(next_cost < dist[next_place]){
        pq.push({next_cost, next_place});
        dist[next_place] = next_cost;
      }
    }
  }
 
}
 

 

 

 

더 아름다운 풀이

 

종만북에는 이와는 다른 아름다운 풀이를 설명해 줍니다...

바로 모든 소방서끼리는 cost 0의 간선으로 연결해 주는 것입니다.

이러한 작업 후 어떤 소방서든 start_startion으로 다익스트라 함수를 한 번만 호출해주면

소방서끼리는 cost 0으로 이동 가능하므로 모든 소방서를 사실상 시작점으로 호출하는 것과 동일한 효과를 만들어 줄 수 있습니다.

 

 

코드