백준 3176 도로 네트워크

LCA를 활용하는 문제이다. 두 도시를 연결하는 경로는 LCA를 통해 구할 수 있다. 두 노드 u, v에서 LCA까지 이르는 경로를 합치면 두 도시를 있는 최소 경로가 된다.

LCA 2 에서는 parents[] 배열에 2^K 번째 부모 노드들을 저장했었는데, 이것을 응용해 2^K 번째 부모 노드까지의 경로에서 에지의 최소값을 저장하는 배열과 최대값을 저장하는 배열을 만들기만 하면 문제를 해결할 수 있다.

LCA 2에서 달라질것은, pathMax[] 배열과 pathMin[] 배열을 새로 만든것과, Parents[] 배열을 초기화하거나 갱신할때 새로 만든 두 배열도 값을 넣어준다는 것, 두 노드의 높이를 맞춰주거나 맞춘 후 위로 탐색할때 u와 v가 움직이는것에 맞춰 탐색되는 경로 상 최대/최소값을 찾아준다는 것이 있다.

---

초기화 시

void initTree(int cur_node, std::vector<std::pair<int, int> > adj[])
{
    for (int i = 0 ; i < adj[cur_node].size(); i++)
    {
        int next = adj[cur_node][i].first;
        int nextPathCost = adj[cur_node][i].second;
        if(depth[next] == -1) //다음 탐색할 노드가 값이 안들어가있는 경우 (자식인 경우)
        {
            depth[next] = depth[cur_node] + 1;
            parents[0][next] = cur_node;
            pathMin[0][next] = nextPathCost;
            pathMax[0][next] = nextPathCost;
            initTree(next, adj);
        }
    }
}

/////////////////////////////

for (int K = 0 ; K < MAX - 1; K++)
    {
        for (int V = 1 ; V < N; V++) // V[0]은 루트.
        {
            if (parents[K][V] != -1) //parents 배열의 해당 자리가 값이 있으면
                parents[K+1][V] = parents[K][parents[K][V]]; //위로 채워나가기;
                pathMax[K+1][V] = std::max(pathMax[K][parents[K][V]], pathMax[K][V]);
                pathMin[K+1][V] = std::min(pathMin[K][parents[K][V]], pathMin[K][V]);
        }
    }

초기화 할때 바로 다음 노드와의 거리를 pathMin, pathMax 배열에 넣어 초기화를 한다.

K값을 늘려 Parents[] 배열을 찾을때도 2^K+1 번째 조상까지의 경로 최소값과 최대값은 2^K 번째 조상에서부터 그 노드의 2^K 번째 조상 까지의 최대/최소값과 현재 노드에서부터 2^K 번째 조상까지의 최대/최소값 중 최대/최소값을 찾아 갱신하게 된다.

두 노드를 옮기거나 탐색하며 경로 최대/최소값 찾기

for (int bit = 0; diff; bit++) // 2진법으로 보고 올림. 
{
    if (diff % 2)
    {
        retMax = std::max(retMax, pathMax[bit][u]);
        retMin = std::min(retMin, pathMin[bit][u]);
        u = parents[bit][u];
    }
    diff /= 2;
}
// 11일경우 1011 2^0, 2^1, 2^3일때, u = parents[bit][u] 실행.

if (u != v)
{
    for (int height = MAX - 1; height >= 0; height--)
    {
        //가장 위 높이서부터 비교 ... 루트는 당연히 공통조상이므로 if에 안걸리고 어느순간 조상이 달라질때 해당 노드로 갱신.
        if (parents[height][u] != -1 && parents[height][u] != parents[height][v])
        {
                        
            retMax = std::max(retMax, std::max(pathMax[height][u], pathMax[height][v]));
            retMin = std::min(retMin, std::min(pathMin[height][u], pathMin[height][v]));
            u = parents[height][u];
            v = parents[height][v];     
        }
        //u, v 갱신하고 왜 height를 다시 높여서 연산하지 않는가?
        //갱신하고 난 뒤, height를 1 높인다 가정하면, 이미 갱신 전에 if에서 걸리지 않은 공통조상이었기 때문에, 그냥 탐색을 이어나가면 됨!
    }
    
    retMax = std::max(retMax, std::max(pathMax[0][u], pathMax[0][v]));
    retMin = std::min(retMin, std::min(pathMin[0][u], pathMin[0][v]));
    u = parents[0][u] ;
}

diff 만큼 올리거나 내릴때도 지금까지의 최대/최소값과 그 옮긴만큼 경로에서의 최대/최소값 중 최대/최소값을 찾는다.

MAX - 1부터 탐색하며 u와 v가 갱신될때도 지금까지 최대/최소값, u와 v가 각각 옮겨진 만큼 의 경로 중의 최대/최소값 중 최대/최소값을 찾는다.

이후 역시 탐색이 끝난 뒤에는 u와 v가 최소 공통 조상 바로 밑 노드를 가지고 있기에, 해당 노드에서 한칸 위의 경로까지 최대/최소값을 비교해서 전체 경로 중 최대/최소값을 찾게 된다.

---

전체 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <string.h>
#include <climits>


const int MAX = 18; //log2(100000) 올림

int parents[MAX][100000];
int pathMin[MAX][100000];
int pathMax[MAX][100000];
int depth[100000];
void initTree(int cur_node, std::vector<std::pair<int, int> > adj[])
{
    for (int i = 0 ; i < adj[cur_node].size(); i++)
    {
        int next = adj[cur_node][i].first;
        int nextPathCost = adj[cur_node][i].second;
        if(depth[next] == -1) //다음 탐색할 노드가 값이 안들어가있는 경우 (자식인 경우)
        {
            depth[next] = depth[cur_node] + 1;
            parents[0][next] = cur_node;
            pathMin[0][next] = nextPathCost;
            pathMax[0][next] = nextPathCost;
            initTree(next, adj);
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0) ; // 입출력 Timeout
    int N;
    std::cin >> N;
    std::vector<std::pair<int, int> > adj[N];

    for (int i = 0; i < N -1 ; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        a--;
        b--;
        adj[a].push_back(std::pair<int, int> (b, c));
        adj[b].push_back(std::pair<int, int> (a, c));
    }
    //int max_h = std::ceil(log2(N));
    memset(parents, -1, sizeof(parents));
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < 100000 ; j++)
            {
                pathMin[i][j] = INT_MAX;
                pathMax[i][j] = INT_MIN;
            }
    }
    std::fill(depth, depth + N, -1);
    depth[0] = 0;
    
    //트리 만들고 parent 초기값 넣기
    initTree(0, adj);

    //parents[K][V] : V노드의 2^k 번째 조상
    //parents[K+1][V] = parents[K][parents[K][V]] : 2^(K+1) == 2*2^K이므로.
    //V의 2^(K+1) 조상은, V의 2^K 조상의 2^K 조상.
    for (int K = 0 ; K < MAX - 1; K++)
    {
        for (int V = 1 ; V < N; V++) // V[0]은 루트.
        {
            if (parents[K][V] != -1) //parents 배열의 해당 자리가 값이 있으면
                parents[K+1][V] = parents[K][parents[K][V]]; //위로 채워나가기;
                pathMax[K+1][V] = std::max(pathMax[K][parents[K][V]], pathMax[K][V]);
                pathMin[K+1][V] = std::min(pathMin[K][parents[K][V]], pathMin[K][V]);
        }
    }
    int C;
    std::cin >> C;
    
    for (int i = 0; i < C; i++)
    {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;

        if (depth[u] < depth[v])
            std::swap(u,v);
        int diff = depth[u] - depth[v];
        int retMax = INT_MIN;
        int retMin = INT_MAX;
        for (int bit = 0; diff; bit++) // 2진법으로 보고 올림. 
        {
            if (diff % 2)
            {
                retMax = std::max(retMax, pathMax[bit][u]);
                retMin = std::min(retMin, pathMin[bit][u]);
                u = parents[bit][u];
            }
            diff /= 2;
        }
        // 11일경우 1011 2^0, 2^1, 2^3일때, u = parents[bit][u] 실행.
        
        if (u != v)
        {
            for (int height = MAX - 1; height >= 0; height--)
            {
                //가장 위 높이서부터 비교 ... 루트는 당연히 공통조상이므로 if에 안걸리고 어느순간 조상이 달라질때 해당 노드로 갱신.
                if (parents[height][u] != -1 && parents[height][u] != parents[height][v])
                {
                               
                    retMax = std::max(retMax, std::max(pathMax[height][u], pathMax[height][v]));
                    retMin = std::min(retMin, std::min(pathMin[height][u], pathMin[height][v]));
                    u = parents[height][u];
                    v = parents[height][v];     
                }
                //u, v 갱신하고 왜 height를 다시 높여서 연산하지 않는가?
                //갱신하고 난 뒤, height를 1 높인다 가정하면, 이미 갱신 전에 if에서 걸리지 않은 공통조상이었기 때문에, 그냥 탐색을 이어나가면 됨!
            }
            
            retMax = std::max(retMax, std::max(pathMax[0][u], pathMax[0][v]));
            retMin = std::min(retMin, std::min(pathMin[0][u], pathMin[0][v]));
            u = parents[0][u] ;
        }
        std::cout << retMin << " " << retMax << "\n"; // +1 처리 안해줘서 틀림.
    }
}

문제를 풀면서 몇번 틀렸던 것은. u와 v가 옮겨지고나서 retMax와 retMin을 비교하도록 짰던 것이 문제가 되었다. 현재 u와 v에서 비교를 해야하는데, u와 v가 갱신이 되고나서 retMax와 retMin을 비교하여 연산하도록 높이맞춰줄때와 위로 탐색해 올라갈때 작성을 했어서 틀렸다.

 

LCA를 한번 풀고 이렇게 하면 되지 않을까? 하는 생각에 조금 삽질하다가 구글링을 살짝쿵 했는데, 그래도 처음 생각했던 방식이 맞아서 기분이 좋다. 이렇게 하루하루 쌓이다보면 더 나은 내가 되지 않을까...

 

오늘도 평온한 하루가 되길. 슨민.