파티

백준 1238

GOLD III

문제 내용
해결 방안
풀이 코드

문제 내용

문제 링크

해결 방안

N개의 마을과 N개의 마을 중 임의의 마을 하나와의 최단 거리를 구하는 문제이다. 단, 각 마을은 유향 그래프로 연결되어 있어 마을 사이를 오고 가는 최단거리가 다를 수 있다. 정리하자면, (N-1)개의 노드에서 임의의 노드로 가는 최단 거리와 임의의 노드에서 (N-1)개의 노드로 가는 최단 거리를 모두 구하고, 두 최단 거리의 합이 가장 큰 노드의 왕복을 위해 소요된 시간을 출력하면 된다.

문제에서 주어진 각 노드 사이의 간선의 가중치는 모두 1~100 사이의 자연수이므로, 다익스트라 알고리즘을 사용할 수 있다. 하지만 각 노드에 대해 다익스트라 알고리즘을 사용하기에는 노드의 개수가 1,000개까지 있을 수 있으며, 왕복까지 총 2번의 반복을 해야 하기 때문에 제한 시간 내에 해결할 수 없다. 하지만, 다익스트라 알고리즘의 과정을 잘 생각해보면, 시작 노드로부터 임의의 정점까지의 최단 거리를 찾는 도중에 방문하는 노드들과의 거리는 모두 최단 거리라는 것을 알 수 있다. 이러한 성질을 이 문제에 적용하면, (N-1)개의 모든 노드들을 방문할 때까지 다익스트라 알고리즘을 수행하여 임의의 노드로부터 직간접적으로 연결된 모든 노드와의 최단거리를 한 번에 구하는 것이 가능하다는 것을 알 수 있다.

반대로, (N-1)개의 노드로부터 임의의 노드까지의 최단 거리는 유향 그래프의 방향성 때문에 위의 방법을 사용할 수 없다. 하지만, 유향 그래프의 방향만 반대로 뒤집으면, 가중치는 그대로인 채로 방향만 임의의 노드에서 (N-1)개의 노드로 가는 그래프가 만들어진다. 결론적으로, 모든 간선들을 입력받으면서 방향만 반대로 뒤집은 간선들을 따로 만들어 저장한 뒤, 두 종류의 간선에 대해 각각 임의의 노드부터 (N-1)개의 노드로 가는 최단 거리를 모두 구하고 각 노드의 최단 거리 합이 가장 큰 노드를 찾으면 된다.

다익스트라 알고리즘(dijkstra algorithm)이란?

그래프 내에서 각 노드 사이에 연결된 간선들 모두가 음의 가중치를 갖지 않는 경우에 대해, 임의의 두 정점 사이의 최단거리를 구하는 알고리즘이다. 알고리즘을 처음 고안안 컴퓨터과학자인 에츠허르 다익스트라의 이름을 따서 명명되었다.

다익스트라 알고리즘을 통해 노드 사이의 최단 거리를 찾는 과정은 다음과 같다.

최단 거리를 구하고자 하는 임의의 한 노드로부터 시작한다.

시작하는 노드의 가중치를 0으로 초기화하고, 그 외의 모든 노드들에는 임의의 큰 값을 부여한다.

현재 노드와 인접한 노드들에 대해 (현재 노드의 가중치 + 인접 노드로의 간선의 가중치)와 인접 노드의 가중치를 비교한다.

만약 인접 노드의 가중치보다 (현재 노드의 가중치 + 인접 노드로의 간선의 가중치)가 더 크면, 해당 노드의 가중치를 갱신한다.

위의 3~4까지의 과정을 아직 방문하지 않은 가장 작은 가중치를 가진 노드에 대해 반복한다.

처음으로 시작 노드 외의 최단 거리를 찾고자 하는 노드에 방문했거나, 방문할 수 있는 모든 노드에 대해 방문했을 경우 반복을 중단한다.

위 과정을 통해 목적지인 노드에 방문했다면 해당 노드의 가중치가 최단 거리이고, 만약 노드의 가중치가 처음에 부여한 임의의 큰 값이라면 노드끼리 직간접적으로 연결되지 않은 것을 의미한다.

결과적으로, 연결된 모든 노드를 방문하고 방문한 노드의 모든 간선에 대해 확인해야 하며(O(V+E)), 간선을 통해 확인한 노드들의 가중치를 통해 다음 노드를 우선순위 큐나 힙으로 결정해야 한다(O(log₂V)). 때문에 연결된 유효한 노드와 간선의 개수가 각각 V와 E라고 한다면, 시간 복잡도는 O((V+E)log₂V)가 나온다.

풀이 코드

#include <iostream>
#include <vector>
#include <map>
#include <queue>

using namespace std;
using Edge = pair<int, int>;
using Weight = pair<int, int>;

// 다익스트라 알고리즘(Dijkstra Algorithm)
vector<int> dijkstra(map<int, vector<Edge>> adjMatrix, int x) {
    // 현재 가장 가중치가 작은 노드를 찾기 위한 우선순위 큐(힙 트리 구조)
    priority_queue<Weight, vector<Weight>, greater<Weight>> heap;
    // 큐에서 꺼낸 값 저장
    Weight top;
    // 임의의 노드 x에서 n개의 노드로 가는 최단 거리를 저장
    vector<int> x2n(1001, 1000000);

    // 시작 노드의 가중치를 0으로 초기화
    x2n[x] = 0;
    heap.push({0, x});
    while(!heap.empty()) {
        // 가장 가중치가 작은 노드
        top = heap.top();
        heap.pop();
        
        // 현재 노드의 가중치가 이미 최단 거리면 알고리즘 수행 안함
        if(x2n[top.second] < top.first)
            continue;

        for(auto h: adjMatrix[top.second]) {
            // 각 노드의 가중치보다 갱신할 가중치가 작으면 노드의 가중치 변경
            // 가중치가 변경되면 갱신할 가중치에 대해 우선순위 큐 갱신
            if(x2n[h.first] > h.second + top.first) {
                x2n[h.first] = h.second + top.first;
                heap.push({h.second + top.first, h.first});
            }
        }
    }
    // 각 노드까지의 최단 거리 반환
    return x2n;
}

int main() {
    // 노드의 개수, 간선의 개수, 임의의 노드 입력
    int n, m, x;
    cin >> n >> m >> x;

    // 간선의 출발 노드, 도착 노드, 가중치 저장
    // 이때, 방향만 반대로 한 간선을 만들어 별도로 저장
    int s, e, t;
    map<int, vector<Edge>> adjMatrix;
    map<int, vector<Edge>> reversedAdjMatrix;
    for(int i = 0; i < m; i++) {
        cin >> s >> e >> t;
        adjMatrix[s].push_back({e, t});
        reversedAdjMatrix[e].push_back({s, t});
    }

    // (n-1)개의 노드에서 x로 가는 최단 거리와
    // x에서 (n-1)개의 노드로 가는 최단 거리 계산
    vector<int> n2x = dijkstra(reversedAdjMatrix, x);
    vector<int> x2n = dijkstra(adjMatrix, x);

    // 두 최단 거리의 합이 가장 큰 노드 탐색 및 출력
    int maxCost = 0;
    for(int i = 1; i <= n; i++) {
        if(maxCost < n2x[i] + x2n[i])
            maxCost = n2x[i] + x2n[i];
    }
    cout << maxCost << endl;
    return 0;
}