[백준] No.11657 - 타임머신 (C++, 벨만-포드)

문제

 

www.acmicpc.net/problem/11657

11657번: 타임머신

 

풀이

 

solved.ac 난이도: Gold 4

 

단일 시작점 최단경로 알고리즘의 대표 격인 다익스트라는 음수 가중치의 간선이 있는 그래프에서는 정확한 값을 구할 수 없다.

그 이유는 음수 사이클이 반복된다면 우선순위 큐에 음의 최단 거리를 가지는 정점이 무한히 업데이트되며 삽입될 것이다.

 

1, 2, 3이 음수 사이클을 이룸.

 

 

따라서 이번 문제와 같이 간선의 가중치로 음수가 주어지는 경우 음수 간선에서도 최단 경로를 구할 수 있는 벨만-포드(Bellma-Ford) 알고리즘을 사용해야 한다.

벨만-포드 알고리즘은 음수 사이클의 존재 여부 또한 알 수 있다.

왜 다익스트라에서는 구할 수 없는 음수에서의 최단 경로를 벨만-포드에서는 구할 수 있는지에 대해서는 jua0610님의 게시글을 참조하자.

 

 

이번 문제 풀이에 사용한 벨만-포드 함수는 다음과 같다.

 

vector<ll> BellmanFord(int start_city){
  vector<ll> upper(city_num+1, INF);
  upper[start_city] = 0;
  bool is_updated = false;
 
  int next_city;
  ll cost;
  for(int iter = 0; iter<city_num ; ++iter){
    is_updated = false;
    for(int now_city = 1; now_city<=city_num ; ++now_city){
      if(upper[now_city] == INF)
        continue;
 
      for(int i = 0; i<adj[now_city].size() ; ++i){
        next_city = adj[now_city][i].first;
        cost = adj[now_city][i].second;
 
        if( cost + upper[now_city] < upper[next_city]){
          upper[next_city] = cost + upper[now_city];
          is_updated = true;
        }
      }
    }
    if(!is_updated) //모든 최단 경로가 구해져 완화가 안되는 경우
      break;
  }
 
  if(is_updated)  //음수 사이클이 존재하여 계속 완화가 가능한 경우
    upper.clear();
  return upper;
}
 

 

벨만-포드에서 음수 사이클의 여부는 최단 경로에 포함 가능한 최대 정점 수(모든 정점의 수 -1)만큼 완화를 진행하였지만, 여전히 완화가 가능한 경우 음수 사이클로 인해 무한히 완화가 가능하다.

따라서 for문이 종료된 시점에서도 is_updated가 true라면 그래프에 음수 사이클이 존재한다는 의미이다.

 

단, 이 문제에는 예외가 한가지 존재하는데

다음과 같이 정상적인 최단 거리를 구할 수 있는 컴포넌트(시작점 포함)와 다른 컴포넌트를 이루는 정점들이 음수 사이클을 이루는 경우이다.

 

만약 위의 코드의 11번 라인과 같이 

upper[now_city] == INF 인 경우에 완화를 건너 뛰지 않는 다면

u와 v는 음수 사이클로 인해 전체 정점의 최단 경로도 무효가 된다.

하지만 문제가 원하는 출력에서는 해당 도시로 가는 경로가 없는 경우 해당 경로의 시간 대신 -1을 출력하면 된다.

따라서 시작점에서 도달할 수 없는 정점은 음수 사이클을 이루더라도 의미가 없어야 한다.

 

upper[now_city] == INF 일 때, 완화를 건너 뛴다면 이러한 정점들은 완화가 진행되지 않고 INF값으로 유지되게 된다.

또한 시작점을 포함하는 컴포넌트의 정점들에서도 INF값에서 다른 정점으로의 최단 경로를 구하더라도 의미 없는 값이므로 최적화에도 효율적이다.

 

 

 

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

참고 풀이:  jua0610님의 게시글

 

코드