[백준] No.13141 - Ignition (C++, 플로이드-와샬)

문제

 

https://www.acmicpc.net/problem/13141

13141번: Ignition

 

풀이

 

solved.ac 난이도: Platium 5

 

플로이드-와샬 알고리즘과 브루트 포스로 해결한 문제.

다익스트라로도 해결 가능하지만 개인적으로는 플로이드-와샬(Floyd-Warshall) 최단 경로 알고리즘을 이용하는 것이 더 깔끔한 것 같다.

 

 

문제 해결을 위해서는 두 가지 정보가 필요하다.

 

1. 각 정점에서 모든 정점까지의 최단 경로

 

이는 플로이드-와샬 알고리즘의 특화 분야이므로 해당 알고리즘을 이용하자.

문제의 입력에서는 두 정점을 직접 연결하는 간선의 수가 여러 개일 수 있다.

하지만 생각해보면 최단 경로를 구하는데 다른 정점으로 이동시 간선이 여러 개라면 가장 짧은 간선을 이용하는 것이 항상 최선의 선택이다.

따라서 각 정점으로의 최단 경로를 구하는 데는 두 정점을 잇는 가장 짧은 간선의 정보만 필요하다.

(구현 코드에서는 이 정보를 dist배열에 저장)

 

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)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

 

 

 

2. 두 정점의 쌍을 잇는 가장 긴 간선의 길이

 

만약 아래의 그래프에서 u정점이 불이 붙는다고 생각해보자.

 

 

u정점이 불에 타는 순간 인접 정점인 v로의 간선에도 동시에 불이 붙는다.

u정점이 불이 붙는 경우 start정점(S)에서 u까지의 최단 경로로 불이 붙을 것이다.

따라서 u가 불타는 시간은 플로이드로 구한 dist[s][u]이다.

 

u에서 v까지의 최단 경로는 길이가 4인 간선을 따라가는 것이므로 불이 v 정점에 닿는 시점은 

dist[s][v] = dist[s][u] + 4일 것이다.

하지만 아직 길이가 6인 간선은 4초만 불타 아직 길이가 2만큼 남았을 것이다.

즉, 두 정점이 불타는 시점에 두 정점을 잇는 간선 중에 가장 늦게 사라지는 간선은 가장 긴 간선이다.

따라서 두 정점의 간선 중에 가장 긴 간선의 정보만 필요하다.

 

u와 v가 모두 불에 타는 시점에 두 정점 사이에 남은 정점의 길이는 다음과 같다.

(두 정점의 간선 중에 가장 긴 간선의 길이를 edge_len이라고 할 때)

 

remain_len = edge_len -(dist[s][v] - dist[s][u]);

 

만약 remain_len이 0 이하라면

 v로 가기 위한 최단 경로에 u가 포함되어 dist[s][v] <= dist[s][u] 인 경우를 의미한다.

 

따라서 remain_len이 0보다 큰 경우(간선이 아직 남아있는 경우)만 계산 해주자.

위와 같은 그래프에서 v가 타는 시점에는 그래프의 양끝에서 선이 타기 때문에 2배로 빨리 사라진다.

그러므로 남은 가장 긴 간선이 사라지는 시간은 remain_len/2 이고

u와 v정점 사이의 모든 간선이 불타 사라지는 시간은 remain_len/2 + dist[s][v] 이다.

(u보다 v에 도달하는데 시간이 오래 걸리기 때문에)

 

두 정점 u, v 사이의 가장 긴 간선의 길이는 adj[u][v]에 저장하기로 하자.

이제 모든 정점을 시작점으로 그래프를 태웠을 때 마지막으로 남은 간선이 사라지는 시간을 비교해

가장 빠르게 그래프를 태울 수 있는 정점을 찾자.

 

double BurnGraph(){
  double shortest_time = INF, longest_time, spent_time, remain_len;
  int edge_len;
 
  for(int start=1; start<=vertex_num ; ++start){
    //start 정점부터 태웠을 때 마지막 간선이 사라지는 시간을 저장
    longest_time = 0; 
 
    for(int from = 1; from<=vertex_num ; ++from){
      for(int to =1; to<=vertex_num ; ++to){
        edge_len = adj[from][to];
 
        if(edge_len != -1){ //from 정점과 간선으로 연결되지 않은 경우
          remain_len = edge_len -(dist[start][to] - dist[start][from]);
 
          //remain_len이 0이하이면 이미 불탄 경우를 의미
          if(remain_len >0){
            spent_time = (remain_len/2) + dist[start][to];
            longest_time = max( spent_time,longest_time);
          }
 
        }
 
      }
    }
    //어떤 정점부터 태워야 가장 빨리 모든 그래프를 태울 수 있는지 저장
    shortest_time = min(longest_time, shortest_time);
  }
  return shortest_time;
} 

 

 

 

코드