[알고스팟] DRUNKEN - 음주 운전 단속 (C++, 플로이드-와샬)

문제

 

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

algospot.com :: DRUNKEN

 

풀이

 

종만북 난이도: 중

 

알고스팟 사이트에는 영문의 문제로 나와있어 당황했지만 종만북의 문제와 동일한 문제가 맞다.

이번 문제는 플로이드-와샬(Floyd-Warshall) 최단 경로 알고리즘을 정확히 이해하고 있어야 해결할 수 있는 좋은 문제였다.

 

플로이드 와샬은 다익스트라나 벨만-포드와 같은 단일 시작점 최단 경로 알고리즘이 아닌 모든 정점의 쌍의 최단 거리를 구할 수 있다.

문제에서는 같은 그래프 안에서 1000개의 테스트 케이스로 두 정점의 최단 거리를 구하려 하므로 플로이드-와샬을 사용해야 한다.

 

단, 문제를 해결하려면 최단 경로 상의 정점들(시작점과 끝점을 제외한)에서 가장 큰 음주 측정 시간을 해당 경로의 최단 시간에 추가해 주어야 한다.

이를 구현하기 위해 플로이드 알고리즘을 변형해보자.

 

플로이드 알고리즘에서는 전체 정점의 집합 S에서 1~K번째 정점을 경유 점으로 추가하며 최단 경로를 갱신하였다.

따라서 다음과 같은 3중 for문으로 간단히 구현할 수 있었는데

 

int adj[501][501]; //간선이 없는 경우 충분히 큰 수로 초기화
void Floyd(){
  for(int k = 1; k<=vertex_num ; ++k)
    for(int i = 1; i<=vertex_num ; ++i)
      for(int j = 1; j<=vertex_num ; ++j)
        adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
      
}

 

adj[i][k] + adj[k][j]는 각각 다음을 의미한다.

adj[i][k]: i정점에서 k정점까지의 최단 거리

adj[k][j]: k정점에서 j정점까지의 최단 거리

 

즉, i에서 바로 j로 가는 최단 거리와 k를 경유해서 가는 최단 거리를 비교하여

adj[i][j]를 더 짧은 거리로 갱신하게 된다.

 

 

이때 K는 1번 정점에서 K번째 정점까지 순차적으로 추가되어 경유하는 최단 거리를 계산한다.

따라서 다음과 같이 더 짧은 거리가 있더라도 3번이 경유 가능 정점 k에 추가되지 않았다면 

3번을 경유하여 4번으로 가는 최단 거리를 구할 수 없다.

 

 

다시 이번 문제로 돌아와서,

문제에 맞게 플로이드를 변형시키기 위해서는 단순히 1~K의 정점을 순차적으로 경유 가능하게 하는 것이 아닌,

예상 소요 시간(교통 체증)이 가장 작은 정점부터 순서대로 경유 가능 점으로 추가하는 것이다.

 

 

만약 정점들이 위와 같은 delay time을 갖는다면 오름차순으로 정렬 시 1, 2, 3, 4, 5 순으로 경유 점에 추가된다.

만약 2까지가 경유 점에 추가되었다면 아직 delay 3인 정점을 경유할 수 없으므로 1->4까지의 최단 예상 시간은 10이 된다.

이후 3이 경유 점에 추가되어야 2(cost of 1->3) + 3(biggest delay) + 1(cost of 3->4) = 6이 최단 예상 시간으로 갱신된다.

 

다음으로 4, 마지막으로 5가 추가되어도 5를 경유하는 경로는 2(cost of 1->5) + 5(biggest delay) + 1(cost of 5->4) = 8으로 1에서 4까지의 최단 예상 시간을 갱신하지 못한다.

 

 

void CalcMaxExpectDist(){
  //측정 시간이 짧게 걸리는 순으로 정렬
  sort(inspection_time, inspection_time+vertex_num);  
 
  for(int k = 0; k<vertex_num ; ++k){
    int via_idx = inspection_time[k].second;
    int delay = inspection_time[k].first;
 
    for(int i = 1; i<=vertex_num ; ++i){
      for(int j = 1; j<=vertex_num ; ++j){
        adj[i][j] = min(adj[i][j], adj[i][via_idx] + adj[via_idx][j]);
        max_expect[i][j] = min(max_expect
        [i][j], adj[i][via_idx] + adj[via_idx][j] + delay);
      }
    }
 
  }
}

 

 

 

코드