【백준】- 13141. Ignition

문제

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

13141번: Ignition

발상이 신기해서 재밌게 풀었습니다. CLASS 6을 찍기 위한 마지막 문제이기도 했고요! 그래서 그런지 이 문제만은 꼭 풀이로 남겨보고 싶었습니다.

 

풀이

최단 거리를 이용하여 푸는 문제라는 것을 떠올릴 수는 있겠지만, 정점이 아닌 간선에 대한 정보를 물어보고 있는 데다가, 그것도 가장 빨리 불타는 간선도 아닌 가장 마지막에 타는 간선에 대한 정보를 묻고 있다보니 혼란스럽지 않을 수가 없는 문제였습니다.

이대로 풀면 복잡하므로 둘로 나누어서 생각해 봅시다. 이 문제를 풀기 위해서는 두 가지 정보가 필요합니다.

 

1. 처음으로 불태우는 정점이 정해졌을 때, 각 정점에 불이 붙는 최단시간은 어떻게 될까?
2. 각 정점에 대해 불타기 시작하는 시간이 정해졌을 때, 두 정점 사이에 있는 모든 간선이 불타는 데 걸리는 가장 오랜 시간은 어떻게 될까?

복잡하니 자세한 설명은 아래에서 하겠습니다. 그리고 예제 1번의 그래프도 사용해 봅시다!

 

1)  각 정점에 불이 붙는 최단시간은 어떻게 될까?

문제에서 묻는 것은 간선이 모두 불타는 데 걸리는 시간이지만, 그래도 우리는 각 정점에 불이 붙는 최단시간은 일반적인 최단경로 문제와 동일하게 구해 주어야 합니다. 간선이 불타는 것은 간선과 연결된 양쪽의 정점 중 최소 한 곳의 정점에서 불이 붙었을 때에야 시작되기 때문입니다. 그래프를 최대한 빠른 시간 안에 태워야 하므로 정점이 불타는 시간을 기록할 때에는 모두 가장 빠른 시간만을 기록하여야 최선의 결과를 얻을 수 있습니다.

 

각 정점에 불이 붙는 최단시간을 구하기 위해서는 두 정점 사이에 간선이 여러 개일 경우, 가장 짧은 길이의 간선만을 생각하시면 됩니다.

또한, 어느 정점에서 불이 붙기 시작하느냐에 따라 각 정점들이 불타기 시작하는 시간이 달라질 수 있고, 이에 따라 결과도 달라질 수 있습니다. 따라서 우리는 모든 경우를 고려해 주어야 합니다.

결국 모든 정점에서 모든 정점으로 이동하는 최단 거리를 구해 줘야 하는 것과 동일한 문제가 되고, 이는 플로이드-워셜 알고리즘을 사용하면 알아낼 수 있습니다.

플로이드-워셜 알고리즘의 시간복잡도는 $O(N^3)$ 으로 비효율적이지만, 정점의 개수도 많아봐야 $200$ 개밖에 안 되기 때문에 충분히 사용할 수 있습니다.

 

$4$ 번 정점부터 태운다고 가정하면, 아래와 같이 각 정점들이 불타기 시작하는 가장 빠른 시각을 알아낼 수 있습니다.

 

+) 정점들에 모두 불이 붙기 전에 간선들이 먼저 타 버리면 말짱 꽝 아닌가요?

풀이를 생각하면서 이런 의문을 가져본 적이 있었지만, 그런 경우는 생길 일이 없다는 것을 알게 되었습니다.

간선이 한쪽으로 타는 경우, 양쪽으로 타는 경우

간선을 모두 불태웠다는 것은, 남은 마지막 간선이 완전히 불탔다는 것과 동일합니다. 이 간선은 양쪽 끝부분에서 불타기 시작해 가운데에서 완전히 탈 수도 있고, 한쪽 끝에서 불타기 시작해 다른 한쪽 끝부분에서 완전히 불탈 수도 있습니다. 각 경우를 고려해 봅시다.

 

• 마지막 간선이 한쪽 끝부분에서 불타기 시작하는 경우 - 다른 한쪽 끝부분에서 완전히 타는 시점에 아직 타지 않은 새로운 정점을 방문하게 됩니다. 이 경우 모든 정점에 불이 붙은 시점과 모든 간선이 불탄 시간은 동일합니다.
• 마지막 간선이 양쪽 끝부분에서 불타기 시작하는 경우 - 양쪽 끝부분에 불이 붙었다는 것 자체가 이미 불이 붙은 정점을 거쳤기에 가능한 것입니다. 이 경우는 간선이 중간 지점에서 완전히 불타게 되고, 그 과정에서 새롭게 방문하게 되는 정점이 없으므로 모든 정점에 불이 붙은 시점보다 모든 간선이 불탄 시간이 늦어지게 됩니다.

따라서, 모든 정점에 불이 붙기도 전에 모든 간선이 불타는 경우는 없음을 증명할 수 있으며, 정점이 불타는 시간을 모두 고려한 뒤 간선이 불타는 시간을 고려해도 괜찮습니다.

 

2. 두 정점 사이에 있는 모든 간선들이 불타는 데 걸리는 가장 오랜 시간은 어떻게 될까?

앞서 우리는 각 정점에 대해 불타기 시작하는 가장 빠른 시각을 알아냈습니다. 각 간선은 양 끝부분이 정점과 연결되어 있으므로, 정점들이 불타는 시각을 활용한다면 간선이 완전히 불타는 시점의 시간도 알아낼 수 있습니다.

 

모든 간선은 양끝에 정점을 가지고, 이 정점들만이 간선이 불타기 시작하는 시간을 좌우합니다

모든 정점들이 서로 간선으로 연결되어 있기에 항상 만족하는 조건입니다. 물론 오른쪽 예시와 같이 양끝에 가지는 정점이 서로 같을 수는 있습니다. 이 간선들에 불이 붙기 시작하는 시간이 언제인지는 오로지 이 두 정점만이 영향을 주게 됩니다.

 

모든 정점 쌍에 대해 간선이 불타는 시간을 모두 조사해 봅시다

그래프에 있는 간선들은 양끝에 속한 정점 번호를 통해, 하나의 순서쌍으로 나타낼 수 있습니다. $1$ 번 정점과 $2$ 번 정점을 양끝에 두는 간선이라면, $(1, 2)$ 와 같이 나타낼 수 있겠죠.

 

여기서 모든 정점 쌍에 대해 연결된 간선들의 타는 시간을 고려한다는 것은, 곧 모든 간선에 대해 불타는 시간을 알아본다는 것과 동일하게 됩니다. 정점이 $N$ 개인 그래프라면, $(1, 1), (1, 2), (1, 3), ..., (1, N), (2, 2), (2, 3), ..., (N, N)$ 와 같이 모든 경우에 대해 연결된 간선들의 타는 시간들을 일일이 계산해 보는 것이죠.

 

모든 경우를 다 고려하는 방법이므로 당연히 정답을 구할 수 있습니다.

 

두 정점과 연결된 간선이 불타는 가장 긴 시간을 고려할 때에는 가장 길이가 긴 간선만 고려해도 됩니다

두 정점과 연결된 간선들은 각 끝점이 타기 시작하는 시간이 모두 동일합니다. 그렇기에 길이가 길 수록 무조건 그 간선이 타는 데 걸리는 시간이 더 오래 걸립니다. 

따라서 양끝의 정점이 정해진 각 경우에 대해서는 가장 길이가 긴 간선 하나만을 고려하는 것으로 충분합니다.

 

간선이 불타는 시간을 계산할 때는 한쪽으로만 타고 있는 경우, 양쪽으로 타고 있는 경우를 고려하여 계산해 줍시다

간선이 완전히 탄 시점의 시간을 알기 위해서는

• 간선이 타기 시작하는 시점의 시간
• 한쪽으로만 간선이 타게 되는 시간
• 양쪽으로 간선이 타게 되는 시간

이 세 정보를 알아야 합니다.

 

위의 예시에서는 두 정점 중 불타기 시작하는 시간대가 빠른 2초인 시점에 간선이 타기 시작했고, 한쪽에서만 타는 시간은 총 1초, 양쪽에서 모두 타는 시간이 총 1.5초로, 4.5초 시점에 간선이 완전히 불탔습니다.

 

• 간선이 타기 시작하는 시점의 시간의 경우 먼저 타기 시작하는 정점의 시간과 동일하고,
• 한쪽으로만 간선이 타게 되는 시간은 두 정점의 타기 시작하는 시간차만큼이고,
• 양쪽으로 간선이 타게 되는 시간은 남은 간선의 길이를 2로 나눈만큼의 시간입니다. 양쪽에서 간선이 타므로 타는 속도도 두 배이기 때문입니다.

이를 이용해 간선이 타는 시간을 계산해 주시면 되겠습니다.

$1$ 번 정점부터 $N$ 번 정점까지 각각의 정점을 시작점으로 잡았을 때, 그리고 각 경우에 대해 모든 가능한 정점 쌍에 대한 간선이 타는 시간을 일일이 구해주더라도, 시간복잡도는 $O(N^3)$ 이기에, 충분히 시간 내에 문제를 풀 수 있습니다.

 

결론 및 전체적인 해결 방법

1. 간선들을 입력받을 때, 간선의 최소 길이, 최대 길이에 대한 정보를 모두 저장합니다. 각 단계에서 사용해야 하니까요. 여담으로 답이 $0.5$ 단위로 나올 수 있기에, 저는 처음부터 모든 간선의 가중치에 $2$ 를 곱한 값을 저장했습니다.
2. 간선의 최소 길이를 이용해 플로이드-워셜 알고리즘을 사용하여 각 정점의 최단 거리를 구합니다. 어느 시작점에서 불타기 시작하느냐에 따라 답이 달라질 수 있기에 해당 알고리즘을 사용했습니다.
3. 모든 $i$ $(1 \le i \le N)$ 번 정점을 출발점으로 하는 각각의 경우에 대해 순서쌍이 $(1, 1), (1, 2), (1, 3), ..., (1, N), (2, 2), (2, 3), ..., (N, N)$ 인 정점을 끝점으로 가지는 간선에 대해 완전히 불타는 시점을 계산합니다. 이런 방식으로 $i$ 번 정점을 출발점으로 할 때의 마지막 간선이 완전히 불타는 시점의 최댓값을 저장해 둔 뒤, 다시 $1, 2, 3, ..., N$ 번 정점을 출발점으로 했을 때의 완전히 간선이 타는 시간의 최솟값을 정답으로 선택하시면 됩니다.

많은 내용을 남김없이 담고 싶다 보니 글이 복잡해지게 됐는데, 이 부분은 죄송스럽게 생각하며 조금이나마 이 글이 도움이 되었으면 하는 바램입니다.

 

코드

• C++17

#include <algorithm>
#include <iostream>
#include <queue>
#define INF 987654321
using namespace std;

int dist[201][201];
int longest[201][201];
int V, E;

void floyd() {
    for (int i = 1; i <= V; i++) {
        dist[i][i] = 0;
    }

    for (int m = 1; m <= V; m++) {
        for (int s = 1; s <= V; s++) {
            for (int e = 1; e <= V; e++) {
                if (dist[s][m] + dist[m][e] < dist[s][e]) {
                    dist[s][e] = dist[s][m] + dist[m][e];
                }
            }
        }
    }
}

void print_answer() {
    int answer = INF;

    for (int i = 1; i <= V; i++) {
        int current = 0;

        for (int a = 1; a <= V; a++) {
            for (int b = 1; b <= V; b++) {
                int l = dist[i][a];
                int r = dist[i][b];

                if (longest[a][b] == 0) {
                    continue;
                }

                int start_time = min(l, r);
                int burn_time = abs(l - r) + (longest[a][b] - abs(l - r)) / 2;

                current = max(current, start_time + burn_time);
            }
        }

        answer = min(answer, current);
    }

    if (answer % 2 == 0) {
        cout << answer / 2 << ".0";
    } else {
        cout << (answer - 1) / 2 << ".5";
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> V >> E;

    fill(&dist[1][1], &dist[V][V + 1], INF);
    fill(&longest[1][1], &longest[V][V + 1], 0);

    for (int i = 1; i <= E; i++) {
        int s, e, d;
        cin >> s >> e >> d;

        dist[s][e] = min(dist[s][e], d * 2);
        dist[e][s] = min(dist[e][s], d * 2);

        longest[s][e] = max(longest[s][e], d * 2);
        longest[e][s] = max(longest[e][s], d * 2);
    }

    floyd();
    print_answer();
}