[백준/C++] 도로 네트워크 (No. 3176)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

먼저 이 문제를 풀기 전에 LCA 2 문제를 풀 수 있다면 이해하는데 도움이 많이 된다.

 

도로 네트워크 문제는 N개의 노드에 대해 N-1개의 간선이 있으며, 다른 도시로 이동할 수 있는 최단 경로가 유일하게 하나 존재한다.

즉, 잘 생각해보면 이 그래프는 트리 구조를 이루고 있다는 사실을 알 수 있다.

 

문제에서 A 도시에서 B 도시로 가는 경우에 최소 비용과 최대 비용을 구하라고 했으며, 경우가 K로 최대 10만이기 때문에 단순 탐색을 반복하면 시간초과가 나게 된다.

 

시간제한 내로 문제를 풀기 위해서 트리를 만들고 최소 공통 조상을 이용해 문제를 풀었다.

 

트리를 만들면 A에서 B로가는 최단 경로는 유일하므로 이는 A와 B를 잇는 경로는 최소 공통 조상을 무조건 거친다는 사실을 알 수 있다.

 

그러므로 A에서 최소 공통 조상으로 가는 경로의 최소비용과 B에서 최소 공통 조상으로 가는 경로의 최소 비용을 비교하면 A에서 B로 이동하는 경로의 최소 비용을 구할 수 있다.

최대 비용도 마찬가지로 쉽게 구할 수 있다.

 

그러면 최소 공통 조상을 어떻게 하면 빠르게 구할 수 있을까?

 

N * N의 이차원 배열을 이용한다면 이분탐색으로 최소 공통 조상을 빠르게 탐색할 수 있겠지만, 10만^2의 배열 공간이 필요하고 기록에도 시간이 오래 걸린다는 문제가 있다.

 

그러므로 애초에 배열의 크기를 NLog(N)으로 만들어 기록에 시간을 줄이고 탐색도 빠르게 하는 방법을 활용하면 된다.

(LCA 2를 풀어보며 최소 공통 조상을 찾는 문제를 풀면 이해에 도움이 된다)

 

먼저 배열 DP를 다음과 같이 정의한다.

DP[ i ][ n ] = i번 노드의 2^n번째 조상을 기록한다.

 

이를 이용하면 DP[ i ][ n + 1 ] = DP[ DP[ i ][ n ] ][ n ] 으로 빠르게 2^n번째 조상도 기록할 수 있다.

 

그림을 통해 생각해보면

 

fig1

 

위와 같은 관계를 갖고 있음을 알 수 있다.

 

이제 DP 배열을 이용해 2^n번째 조상들을 쉽게 구한다면, 마찬가지로 2^n번째 조상들에 방문하는 경로의 최소 비용과 최대 비용을 기록할 수 있다.

 

ex)

DP[ i ][ n+1 ]로 가는 최소 비용 =

min( DP[ i ][ n ]으로 가는 최소 비용 , DP[ DP[ i ][ n ] ][ n ] (DP[i][n]의 2^n번째 조상으로 가는 최소 비용)

 

이제 i번 노드의 2^n번째 조상들을 구했고, 그 조상에 도착하는데 드는 비용들을 계산했다면 A노드와 B 노드의 최소 공통 조상을 찾기만 하면 된다.

 

찾는 방법은 이분탐색으로 구하면 된다.

n을 순차적으로 탐색할 경우 A와 B의 2^n번째 공통조상이 같다면, 2^(n-1) 조상이 다르다는 뜻이다.

 

그러므로 2^(n-1) 조상으로 이동해 A, B의 최소 공통조상을 찾는 과정을 반복하면 된다.

(A와 B가 다르면서 바로 위 조상이 같을 때 까지 찾으면 됨)

 

이렇게 최소 공통을 찾는 과정에서 비용을 비교하며 최대 최소 비용을 구한 다음 출력하면 된다.

 

 

[아이디어 정리]

1. 그래프가 트리의 형태이며, 최단경로가 유일하므로 두 노드가 최소 공통 조상으로 도착하는 데 드는 비용을 비교하는 문제로 풀 수 있다.
2. 최소 공통 조상을 빠르게 찾기 위해 DP[i][n]을 i번 노드의 2^n번째 조상으로 정의한다.
3. DP 배열을 이용해 최소 공통 조상을 찾아가는 과정에서 최소 비용과 최대 비용을 비교해 기록한다.
4. 최소 공통을 찾았다면, 그 동안 구한 최소비용과 최대비용을 출력한다.

 

 

Code

 

 

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int INF = 1987654321;
struct nmm
{
    int n;
    int minV;
    int maxV;
};

void conv(nmm &tM, int taD, vector<int> &dpt, vector<vector<nmm>>&DP)
{
    nmm tmp;
    while(dpt[tM.n]>taD)
    {
        for (int i=0; i<=20; i++)
        {
            tmp = DP[tM.n][i];
            if (tmp.n==0)
            {
                tmp = DP[tM.n][i - 1];
                tM.n = tmp.n;
                tM.minV = min(tM.minV, tmp.minV);
                tM.maxV = max(tM.maxV, tmp.maxV);
                break;
            }
            if (dpt[tmp.n]==taD)
            {
                tM.n = tmp.n;
                tM.minV = min(tM.minV, tmp.minV);
                tM.maxV = max(tM.maxV, tmp.maxV);
                return;
            }
            else if (dpt[tmp.n] < taD)
            {
                tmp = DP[tM.n][i - 1];
                tM.n = tmp.n;
                tM.minV = min(tM.minV, tmp.minV);
                tM.maxV = max(tM.maxV, tmp.maxV);
                break;
            }
        }
    }
    return;
}

nmm findC(nmm mA, nmm mB, vector<vector<nmm>>& DP)
{
    nmm tmp;

    tmp.n = 0, tmp.minV = min(mA.minV, mB.minV), tmp.maxV = max(mA.maxV, mB.maxV);
    if (mA.n==mB.n)
    {
        return tmp;
    }
    int a, b;
    a = mA.n, b = mB.n;
    while(true)
    {
        if (DP[a][0].n==DP[b][0].n)
        {
            tmp.minV = min({ tmp.minV, DP[a][0].minV,DP[b][0].minV });
            tmp.maxV = max({tmp.maxV, DP[a][0].maxV, DP[b][0].maxV});
            return tmp;
        }
        for (int i=1; i<21; i++)
        {
            if (DP[a][i].n==DP[b][i].n)
            {
                tmp.minV = min({ tmp.minV, DP[a][i - 1].minV, DP[b][i - 1].minV });
                tmp.maxV = max({ tmp.maxV, DP[a][i - 1].maxV, DP[b][i - 1].maxV });
                a = DP[a][i - 1].n;
                b = DP[b][i - 1].n;
                break;
            }
        }
    }
    return tmp;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N,K;
    cin >> N;
    vector<vector<pair<int,int>>> graph(N + 1);
    vector<int> dpt(N + 1, 0);
    nmm tmp;
    tmp.n = 0, tmp.minV = INF, tmp.maxV = 0;
    vector<vector<nmm>>DP(N + 1, vector<nmm>(21, tmp));

    int a, b,c;
    for (int i=1; i<N; i++)
    {
        cin >> a >> b>>c;
        graph[a].push_back({ b,c});
        graph[b].push_back({ a,c });
    }
    cin >> K;
    queue<pair<int,int>> q;
    q.push({1,0});
    vector<bool> visited(N + 1, false);
    visited[1] = true;
    pair<int, int> np,nxtP;
    int node;
    while(!q.empty())
    {
        np = q.front();
        q.pop();
        node = np.first;
        for (int i=0; i<graph[node].size(); i++)
        {
            nxtP = graph[node][i];
            if (!visited[nxtP.first])
            {
                visited[nxtP.first] = true;
                int j = 0;
                DP[nxtP.first][j].n = node;
                DP[nxtP.first][j].minV = min(DP[nxtP.first][j].minV, graph[node][i].second);
                DP[nxtP.first][j].maxV = max(DP[nxtP.first][j].maxV, graph[node][i].second);
                while (DP[DP[nxtP.first][j].n][j].n != 0)
                {
                    DP[nxtP.first][j + 1].n = DP[DP[nxtP.first][j].n][j].n;
                    DP[nxtP.first][j + 1].minV = min(DP[nxtP.first][j].minV, DP[DP[nxtP.first][j].n][j].minV);
                    DP[nxtP.first][j + 1].maxV = max(DP[nxtP.first][j].maxV, DP[DP[nxtP.first][j].n][j].maxV);
                    j++;
                }
                dpt[nxtP.first] = np.second + 1;
                q.push({ nxtP.first, dpt[nxtP.first] });
            }
        }
    }
    
    for (int i = 0; i < K; i++)
    {
        cin >> a >> b;
        nmm mA, mB;
        mA.n = a, mA.minV = INF, mA.maxV = 0;
        mB.n = b, mB.minV = INF, mB.maxV = 0;
        if (dpt[a]>dpt[b])
        {
            conv(mA, dpt[mB.n], dpt, DP);
        }
        else if (dpt[a]<dpt[b])
        {
            conv(mB, dpt[mA.n], dpt, DP);
        }
        nmm ans = findC(mA, mB, DP);
        cout << ans.minV << " "<<ans.maxV << "\n";
    }
    return 0;
}

 

---

 

DP 배열을 기록하고 갱신하는 과정에서 최상단 노드에서 오류가 떠서 생각보다 푸는데 오래 걸렸던 문제였다.

압축한 값을 기록하는 방법에 익숙해지면 다른 문제를 풀 때도 많은 도움이 될 것 같다

 

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