[알고스팟] NTHLON - 철인 N종 경기 (C++, 다익스트라)

문제

 

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

algospot.com :: NTHLON

 

 

풀이

 

종만북 난이도: 상

 

다익스트라를 이런 식으로도 이용이 가능하다는 것을 알 수 있는 좋은 문제.

그만큼 어렵다...

 

이번 문제에서 가장 중요한 것은 종목의 진행 순서는 총 코스 소요시간과 상관이 없다는 것이다.

즉, 각각의 종목을 정점으로 설정하여 경로를 만드는 것은 결국 종목의 진행 순서를 만드는 것이므로 이러한 구현이 필요가 없다.

더군다나 이러한 구현의 시간 복잡도는 시간 안에 문제를 해결하지 못한다.

 

모든 종목들이 가능한 순서를 정하여 이를 계산해 보려면 

종목이 최대 500개 이므로 한 종목(정점)을 선택 후 가능한 다음 선택지는 500개이다.

따라서 종목 n개를 선택하여 비기는 코스를 찾는 경우의 수는 500^n으로 

수행 가능한 최대 종목 수는 정해져 있지 않은 상태에서는 너무 큰 복잡도를 갖는다.

 

종목에 관계 없이 중요한 데이터는 해당 종목에 의해 발생하는 A와 B선수의 기록 차이(Gap)이다.

어떤 종목이 되든, 17(A) 15(B)와 32(A) 30(B)의 차이는 2로 같다.

따라서 A선수를 기준점으로 잡고 B 선수와 종목에서의 시간 차이를 정점을 나타내 보자.

두 선수의 기록에서 발생 가능한 차이는 A가 최소이고 B 가 최대일 때 -199에서

A가 최대이고 B가 최소일 때의 +199이다.

따라서 -200 ~ 200의 값을 나타내는 400개의 정점이 필요하다.

 

이제 각 정점에서 어떤 식으로 간선을 뻗어 그래프를 생성할지 생각해보자.

사실 어떤 종목을 실행하였든 다음에 선택 가능한 종목에는 제한이 없다.

따라서 각 정점(n)에서 모든 종목의 차이(gap)를 더한 정점(n-gap)으로 간선을 생성한다. 

또한 문제의 답을 구하기 위해 사용하는 간선의 가중치는 해당 종목의 A선수의 기록이다.

gap이 0이 되는 코스에서는 결국 A의 기록 합과 B의 기록 합이 같기 때문에 A선수의 기록을 가중치로 설정하든 B의 기록의 가중치로 설정하든 결과는 같다.

 

자, 그렇다면 다익스트라를 진행하기 위해서는 어느 점이 시작점이 되고 어느 점이 도착점이 되어야 할까?

목적지는 코스의 기록 합의 차이가 0인 정점 0을 향해야 한다.

다익스트라 최단 경로 알고리즘은 단일 시작점 알고리즘 이기 때문에 처음 선택하는 모든 종목들의 gap이 시작 정점이 될 수 있다.

이러한 구현을 위해 모든 정점을 시작점으로 다익스트라를 여러 번 진행하기보다는 더미 부모 노드를 두어 시작 정점들과 연결을 해주자.

이러면 더미 부모 노드에서 다익스트라를 진행하면 바로 모든 시작 정점들로 이동 가능하다. 

 

const int START_IDX = 401;
 
 int gap;
 for(int i= 0; i<event_num ; ++i){
   gap = event_timeA[i] - event_timeB[i];
   time_gap[i] = gap;
   adj[START_IDX].push_back({event_timeA[i], Vertax(gap)});
 }

 

이러한 그래프의 구현은 gap이 -100인 종목으로 간선으로 통해 계속 이동한다면 -200 이상의 정점으로 접근할 수도 있다.

하지만 생각해보면 -200 이하로 진행하는 것은 최단 경로에 의미가 없는 계산이다.

정답인 코스 합의 차가 0인 정점 0으로 이동하기 위해서는,

항상 -200이하로 내려가기 전에 +gap을 경로에 추가해주는 것이 항상 최단 경로를 구하는 것에 손해가 없다.

 

따라서 다음 종목의 선택으로 gap의 절댓값이 200 이상이 된다면 해당 경로는 취소해주자.

 

이러한 음수 gap을 정점으로 나타내기 위해 각 정점의 값에 +200씩을 해주는 것을 주의하자.

 

 

int FindMinDraw(){
  vector<vector<pair<int,int>>> adj(402);
 
  int gap;
  for(int i= 0; i<event_num ; ++i){
    gap = event_timeA[i] - event_timeB[i];
    time_gap[i] = gap;
    adj[START_IDX].push_back({event_timeA[i], Vertax(gap)});
  }
 
  int next_idx;
  for(int vertax_idx = -200; vertax_idx<=200 ; ++vertax_idx){
    for(int event_idx = 0; event_idx<event_num ; ++event_idx){
      next_idx = vertax_idx + time_gap[event_idx];
 
      if(abs(next_idx)>200) 
        continue;
 
      adj[Vertax(vertax_idx)].push_back({ event_timeA[event_idx], Vertax(next_idx)});
    }
  }
 
  int ret = Dijkstra(adj);
  if(ret == INF)
    return  -1;
 
  return  ret;
}

 

 

참고 서적: 알고리즘 문제 해결 전략(구종만 저)

코드