[백준/Baekjoon] Ignition 13141 C++ :: Graph & Floyd_warshall

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

13141번: Ignition

---

1. Logic

1 ~ n번까지의 정점을 순서대로 다 불을 붙혀보면서 그중에서 전부 연소하는데 걸리는 최소 시간을 구하면 됨.

 

가장 중요한 모든 그래프를 연소시키는 최소 시간을 구하는 법에 대해 설명할 것이다.

먼저 각 정점에서 모든 정점까지의 최단 경로를 알아햐 한다. 

문제의 테스트케이스 1번을 보면 두개의 정점을 연결하는 동일한 간선이 존재할 수도 있다. 이럴경우는 가장 짧은 간선을 이용하여 연소하는 것이 최선의 방법이므로 플로이드 와샬 알고리즘을 통해 내 코드에서는 dist배열에 저장한다.

 

두번째로는 두개의 정점을 연결하는 가장 긴 간선의 길이를 알아야한다. 문제에서 모든 간선을 태워야 한다고 했으므로 우리는 앞에서 플로이드 와샬로 최단거리를 구했지만 최단거리 이외에 더 긴 간선까지 연소돼야 조건에 맞으므로 긴 간선의 길이를 구해야한다. 

 

이 그래프에서  S에 불을 붙힌 후 연소하는 시간을 살펴보면 S에서 M까지 연소하는 시간은 플로이드 와샬로 구한 최단거리인 2일것이다. 2초후에는 s > M간선이 다 연소하고 M > E로 가는 간선 2개에 불이 붙을 것이다. 

M에서 E로 가는 간선은 두개인데 같이 불이 붙기 때문에 M번 노트에서 불이 붙은 3초 후에는 아래와 같은 그림이 생성된다. 

M에서 E까지의 최단경로는 S에서M까지 가능 경로 + M에서 E까지 가는 최단 경로이기 때문에 식으로 표현하게 되면 dist[S][E] = dist[S][M] + 3이 된다.하지만 우리는 모든 그래프를 태워야 하기 때문에 3초가 지날 동안 5초짜리 간선이 3/5밖에 안탔다.

두개의 정점을 이은 간선중 가장 길이가 긴 정점을 longestEdge라고 한다면 두 정점이 연소하는 사이 남은 간선의 길이는

remainLen = longestEdge - (dist[S][E] - dist[S][M])이라고 나타낼 수 있다.

 

만약에 remainLen이 0이하라면 E로 가기 위한 최단 경로에 M이 포함되어있는 경우를 의미한다.(M을 거쳐서 가는것보다 S에서 E로 바로 가는 더 짧은 경로가 존재함)

또한 M에서 E로 가는 간선은 시간 차이가 있기 때문에 3초후 E와 연결되어 있는 아직 연소중인 M>E간선은 E노드 끝에서도 같이 연소하여 2배로 빨리 연소하게 된다.

그렇기 때문에 남은 가장 긴 간선이 사라지느 시간은 reaminLen/2이고 S와 E정점 사이의 모든 간선이 불타 사라지는 시간은 remainLen/2 + dist[S][E]가 된다.

 

위의 설명을 읽으면서 코드를 보면 이해하기 쉬울 것이다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m;
const int INF = 0x3f3f3f3f;

vector<vector<int>> graph(201, vector<int> (201, -1));
//최단거리 배열
vector<vector<int>> dist(201, vector<int> (201, INF));

double burn() {
    double shortestTime = INF;
    double longestTime, spentTime, remainLen;
    int longestEdge;

    for(int start=1; start <= n; ++start) {
        //start 정점부터 태웠을 때 마지막 간선이 사라지는 시간
        longestTime = 0;

        for(int from = 1; from <= n; ++from) {
            for(int to = 1; to <= n; ++to) {
                longestEdge = graph[from][to];

                if(longestEdge != -1) {
                	//간선이 있을 때 존재하는 간선의 길이
                    remainLen = longestEdge - (dist[start][to] - dist[start][from]);

                    //양쪽 끝에서 불이 붙은 경우
                    //다른 긴 간선이 존재하는 경우
                    if(remainLen > 0) {
                        spentTime = (remainLen / 2) + dist[start][to];
                        longestTime = max(spentTime, longestTime);
                    }
                }
            }
        }
        shortestTime = min(longestTime, shortestTime);
    }
    return shortestTime;
}

void floyd() {
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;

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

    for(int i = 0; i < m; i++) {
        int s, e, l;
        cin >> s >> e >> l;
        //동일한 위치로 가는 간선일 때는 제일 선분만 있으면 됨.
        dist[s][e] = min(dist[s][e], l);
        dist[e][s] = dist[s][e];

        graph[s][e] = max(graph[s][e], l);
        graph[e][s] = graph[s][e];
    }

    //플로이드로 최단거리 구하기
    floyd();

    cout << fixed;
    cout.precision(1);
    cout << burn();
}

 

 

---

3. Feedback

그래프 플레티넘 문제 어렵다,,,,

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐