Ignition( BOJ 13141 )

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

13141번: Ignition

 

문제 파악하기

모든 간선을 불 태우는데 걸리는 최소 시간을 구하는 문제입니다. 보통 그래프 문제들은 정점에 초점을 맞췄다면 이번 문제는 간선에 초점을 맞춘 문제라고 할 수 있습니다. 간선은 인접한 정점에 불이 붙으면 1초에 1씩 불타며, 양 끝의 정점이 모두 불이 붙었다면 양쪽에서 불타게 됩니다. 문제를 해결하기 위해서는 어떤 정점부터 불을 붙을지 보다는 한 정점에서 불을 붙였을 때, 걸리는 시간을 구하는 알고리즘을 먼저 구해야 합니다. 정점을 선택하는 건 이후에 저절로 구할 수 있습니다. 문제를 해결하는 알고리즘을 단계별로 하나씩 살펴보도록 합시다.

 

문제 해결하기

우선, 임의의 정점에 불을 붙였을 때 모든 간선이 불타는데 걸리는 시간을 구해봅시다. 문제를 좀 더 쉽게 해결하는 방법은 간선에 초점을 맞추는 것입니다. 정점에 초점을 맞춰서 그래프를 바라보면 상당히 복잡합니다. 각각의 간선이 불타는 데 걸리는 시간은 조그만 생각하면 쉽게 알 수 있습니다. 정점 A와 B를 연결한 간선을 (A, B)라고 표현해보겠습니다. (A, B)가 모두 불타기 위해서는 시작 정점부터 출발한 불이 정점 A 혹은 정점 B에 도달해야 합니다. 결국, 간선 (A, B)가 불타기 시작하는 시간은 정점 A와 B 중 먼저 도착한 시점부터입니다. 불타기 시작한 시점을 구한 다음에는 간선이 모두 불타는데 걸리는 시간을 구할 수 있습니다. 이 경우, 우리는 2가지 경우만을 고려하면 됩니다. 첫 번째, 미리 도착한 정점에서 불이 시작해서 간선을 모두 태우는 경우입니다. 건너편 정점에 불이 늦게 도착할 경우, 즉 간선의 두 정점에 불이 도착하는 시간의 차이가 간선의 길이보다 큰 경우에는 간선의 길이만큼 시간이 걸립니다. 두 번째, 간선이 타고 있는 중간에 건너편 정점에 불이 도착해서 양쪽에서 간선을 태우는 경우입니다. 이 경우에는 이미 태워버린 길이를 제외하고 나머지 길이를 2씩 태우기 때문에 ( 지금까지 태운 길이 + 남은 길이/2 )만큼의 시간이 걸리게 됩니다.

 

이렇게 각각의 간선이 타는데 걸리는 시간을 구하는 방법을 살펴보았습니다. 위에서 위의 알고리즘만 구하면 저절로 어떤 정점에서 시작해야 할지 알 수 있다고 말했는데 사실일까요? 힌트는 바로 소스코드로 구현된 알고리즘에 숨어있습니다. 위의 알고리즘을 소스코드로 작성해보면 단순 반복문으로 충분히 구현할 수 있습니다. 이 말은 즉, 모든 정점에 불을 한번씩 붙여보아도 충분하다는 의미입니다! 정점의 개수는 최대 200개이며, 간선의 개수는 최대 20,000개이기 때문에 중첩 반복문으로 모든 경우의 수를 살펴보아도 1초 내에 충분히 살펴볼 수 있습니다. 각각의 정점에서 다른 정점으로 갈 수 있는 최단 경로를 구한 다음, 각각의 정점을 기준으로 불을 붙였을 때 타는데 가장 오래 걸리는 간선을 탐색해보면 우리가 원하는 정답을 구할 수 있습니다.

 

소스코드

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <utility>
#include <algorithm>
#define NMAX 205
#define INF 20005
#define PAIR pair<pair<int, int>, int>
using namespace std;
 
int N, M, S, E, L;
int dst[NMAX][NMAX];
vector< PAIR > edges;
 
int a, b, len, diff;
double tmp, ret;
 
int main() {
    // 그래프 초기화
    for(int i=1;i<NMAX;i++)
        for(int j=1;j<NMAX;j++) dst[i][j] = INF;
    
    // 입력
    scanf("%d %d", &N, &M);
    for(int i=1;i<=M;i++) {
        scanf("%d %d %d", &S, &E, &L);
        
        edges.push_back({{S, E}, L});
        dst[S][E] = dst[E][S] = min( dst[S][E], L );
    }
    
    // 플로이드 알고리즘
    for(int k=1;k<=N;k++) {
        for(int i=1;i<=N;i++) {
            if(dst[i][i] == INF) dst[i][i] = 0;
            
            for(int j=1;j<=N;j++) {
                dst[i][j] = min( dst[i][j], dst[i][k] + dst[k][j] );
            }
        }
    }
    
    ret = INF;
    for(int sel=1;sel<=N;sel++) {
        tmp = 0;
        
        // 각각의 정점에서 모든 간선 확인하기
        for(int i=0;i<M;i++) {
            a = edges[i].first.first;
            b = edges[i].first.second;
            len = edges[i].second;
            
            // 정점 사이의 도착 시간 차이
            diff = abs(dst[sel][a] - dst[sel][b]);
            
            // min(dst[sel][a], dst[sel][b]) : 먼저 도착하는 정점까지의 시간
            // diff: 정점 1개에서 태우는 시간 / (len-diff)/2.0: 정점 2개에서 태우는 시간
            if(diff <= len) tmp = max( tmp, min(dst[sel][a], dst[sel][b]) + diff + (len - diff)/2.0 );
            else tmp = max( tmp, min(dst[sel][a], dst[sel][b]) + (double)len );
        }
        
        ret = min( ret, tmp );
    }
    
    // 출력
    printf("%.1lf", ret);
}
 

후기

간선에 초점을 맞춘다는 생각이 재미있는 문제였습니다. 단순히 각각의 정점에서 BFS로 해결하는 문제보다 훨씬 재미있게 풀었습니다. 최단 경로 알고리즘과 그래프 문제를 연습하는 사람에게 추천하고 싶은 문제입니다.