[C++ 백준 풀이][Platinum II] 15480번 : LCA와 쿼리 (LCA 알고리즘 응용)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 15480번 : 'LCA와 쿼리' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum II에 해당하며, LCA(최소 공통 조상) 알고리즘에 대해 알고 있어야 합니다.

 

 

15480번 : LCA와 쿼리

 

N개의 노드로 이루어져 있는 트리의 간선들이 모두 입력되었을 때, r u v(루트 노드를 r이라고 설정했을 때 u와 v의 LCA를 출력) 쿼리에 대한 처리를 수행하는 문제입니다.

우선 노드의 수가 10만개 이하이므로, LCA 알고리즘을 사용하여 최소 공통 조상을 log H 시간 안에 찾아야 함은 예상이 가능합니다.

문제는 루트 노드가 매 쿼리마다 바뀐다는 것인데, 상식적으로 생각해보아도 루트를 매번 재설정하면 시간 초과가 될 것이 분명하기 때문에 루트를 그대로 유지하면서 r u v에 대한 처리를 수행하는 방법을 생각해야 합니다.

 

 

#include <cstdio>
#include <vector>
#define MAX 100001
using namespace std;
 
int Parent[MAX][20], Depth[MAX], H = 0;
vector<int> Line[MAX];
 
void findParent(int Par, int Node, int Dep) {
    if(!Line[Node].size()) return;
    Parent[Node][0] = Par;
    Depth[Node] = Dep;
    for(int i=0; i<Line[Node].size(); i++)
        if(Line[Node][i] != Par) findParent(Node, Line[Node][i], Dep+1);
}
 
int findLCA(int A, int B) {
    if(Depth[A] != Depth[B]) {
        if(Depth[A] < Depth[B]) swap(A, B);
        int Diff = Depth[A] - Depth[B];
        for(int i=0; Diff>0; i++) {
            if(Diff%2) A = Parent[A][i];
            Diff >>= 1;
        }
    }
    if(A != B) {
        for(int i=H; i>=0; i--)
            if(Parent[A][i] != 0 && Parent[A][i] != Parent[B][i]) {
                A = Parent[A][i];
                B = Parent[B][i];
            }
        A = Parent[A][0];
    }
    return A;
}
 
int main() {
    int N, M, A, B, r, u, v;
    int temp, r_temp, u_temp, v_temp, maxNode;
    scanf("%d", &N);
    temp = N;
    while(temp > 1) {
        temp /= 2;
        H++;
    }
    for(int i=0; i<N-1; i++) {
        scanf("%d %d", &A, &B);
        Line[A].push_back(B);
        Line[B].push_back(A);
    }
    findParent(0, 1, 0);
    for(int i=1; i<=H; i++)
        for(int j=2; j<=N; j++)
            if(Parent[j][i-1]) Parent[j][i] = Parent[Parent[j][i-1]][i-1];
    scanf("%d", &M);
    for(int i=0; i<M; i++) {
        scanf("%d %d %d", &r, &u, &v);
        u_temp = u, v_temp = v;
        int uvLCA = findLCA(u_temp, v_temp);
        u_temp = u, r_temp = r;
        int urLCA = findLCA(u_temp, r_temp);
        v_temp = v, r_temp = r;
        int vrLCA = findLCA(v_temp, r_temp);
        maxNode = Depth[uvLCA]>Depth[urLCA]?uvLCA:urLCA;
        maxNode = Depth[maxNode]>Depth[vrLCA]?maxNode:vrLCA;
        printf("%d\n", maxNode);
    }
}
 

 

우선 루트 노드를 1번 노드로 가정하고 일반 LCA 문제와 같이 Parent와 Depth를 설정해줍니다.

O(log H) 시간에 Parent를 찾을 수 있는 알고리즘은 아래의 링크에서, 문제를 해결하면서 자세히 설명해두었습니다.

 

[C++ 백준 풀이] 3584번 : 가장 가까운 공통 조상 (Easy LCA)

 

이제 생각해보아야 할 것은 루트를 변경시키지 않고 어떻게 루트를 r로 변경시킨 것과 같은 연산을 수행할 수 있느냐는 것입니다.

이것은 트리 자체는 r번 노드가 루트 노드인 것처럼 그려놓고, 1번 노드가 있을 수 있는 위치를 모두 경우를 나눠서 확인해보면 됩니다.

 

 

그림이 상당히 퀄리티가 낮은데, 패드가 없어서 그림판에 터치패드로 그려서 그렇습니다.

 

어쨌든 지금 하려는 것은 r번 노드를 루트인 것처럼 그렸지만, 실제로는 1번 노드가 루트 노드일 때 어떻게 답을 구할지 생각하는 것입니다.

1번 노드가 위치할 수 있는 경우는 위의 그림에서 1~6번까지 총 6가지가 있습니다.

 

1번 노드의 위치에 따라 다음과 같이 나눠서 생각해볼 수 있습니다.

위치 1에 있는 경우 : LCA(u, r)과 LCA(v, r) 모두 루트인 1번 노드가 되고, 우리가 구하고자 하는 LCA(u, v)가 가장 깊이 위치합니다.

위치 2에 있는 경우 : LCA(u, r)과 LCA(v, r) 모두 r번 노드가 되고, 구하고자 하는 LCA(u, v)가 역시 가장 깊이 위치합니다.

위치 3에 있는 경우 : LCA(u, v)와 LCA(v, r) 모두 1번 노드가 되고, 구하고자 하는 노드는 여기서는 LCA(v, r)이 되며 가장 깊이 위치합니다.

위치 4에 있는 경우 : 위치 3과 마찬가지로 생각하되 LCA(u, r)이 답이 되고 가장 깊이 위치하는 건 똑같습니다.

위치 5에 있는 경우 : 구하고자 하는 노드는 LCA(v, r)이며 가장 깊이 있습니다.

위치 6에 있는 경우 : 똑같이 생각하면 되며 구하고자 하는 노드는 LCA(u, r)이고 가장 깊이 위치합니다.

 

구해보면 6가지 경우 모두 LCA(u, v), LCA(u, r), LCA(v, r) 중 가장 깊이 있는 노드가 답이 됩니다.

따라서 3번의 LCA 연산 수행 후 가장 Depth가 큰 노드의 번호를 출력해주면 됩니다.

 

이것을 구현한 것이 메인 함수에서 아래 부분의 코드에 해당합니다.

 

 

 

풀이를 제출해보면 시간 초과 없이 제한 시간 안에 충분히 통과가 가능함을 확인할 수 있습니다.