[백준/BOJ] 11438번: LCA 2 ( 최소 공통 조상 구하기 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/11438

 

풀이

이 문제는 그래프가 주어졌을 때, 임의의 두 정점의 최소 공통 조상( lowest common ancestor )을 찾는 문제입니다.

여기서, 최소 공통 조상이란, 선택된 두 정점의 조상 중에서 가장 큰 깊이( depth )를 가진 정점을 말합니다.

 

최소 공통 조상을 구하는 알고리즘은 여기에서 볼 수 있습니다.

[C++] 최소 공통 조상( lowest common ancestor, LCA ) 구하기

 

먼저, 문제의 입력값으로부터, 그래프를 구성하고, 너비 우선 탐색( BFS )을 통해서, 각 노드의 깊이와 바로 위의 부모를 구합니다.

#define SIZE    100000
#define MAX_LEVEL  17

vector<int> graph[SIZE+1];	
bool visited[SIZE+1];
int depth[SIZE+1];			// 각 노드들의 깊이
int parent[MAX_LEVEL+1][SIZE+1];	// 각 노드들의 조상 노드 저장

// 너비 우선 탐색
void BFS( int start){
    
    queue<int> q;

    visited[start] = true;
    
    int next_level = 1; // 노드의 깊이
    int level_size = 1; // 현재 깊이에 있는 정점의 개수
    int cnt = 0;

    q.push(start);

    while( !q.empty()){
        int vert = q.front();
        q.pop();

        for( int x : graph[vert] ){
            if ( !visited[x] ){
                visited[x] = true;
                parent[0][x] = vert;    // 정점의 부모 노드
                depth[x] = next_level;  // 정점의 깊이
                q.push(x);
            }
        }

        cnt++;
        if ( cnt == level_size){    // 다음 깊이 단계로 진행
            cnt = 0;
            next_level++;
            level_size = q.size();
        }
    }
}

//----------------------------------------------------------------
// main 함수

int N;
N = readInt();	// 정점의 개수

int a, b;
for( int i = 1; i < N; i++){
    a = readInt();
    b = readInt();

    graph[a].push_back(b);	// 그래프 구성
    graph[b].push_back(a);
}

BFS(1);	// 노드들의 깊이와 바로 위의 부모 노드 계산

 

위의 정보를 갖고, 필요한 parent 배열의 값을 계산합니다.

int kmax;

void SetupAncestor(int N){
    
    int val = 1;
    while( val <= N){
        val <<= 1;  
        kmax++;	// kmax 값 계산
    }

    // 현재 노드에서 조상 노드로 점프하기 위한 값들을 계산
    for( int k = 1; k <= kmax; k++){
        for( int n = 1; n <= N; n++){
            parent[k][n] = parent[k-1][ parent[k-1][n] ];
        }
    }
}

 

이제, 선택된 두 정점의 최소 공통 조상( LCA )를 찾으면 됩니다.

위의 알고리즘을 설명한 글에선, LCA를 찾기 과정을 설명하기 위해, 두 개의 함수로 분할해서 구현했지만,

이 글에선, 분할된 함수들을 합쳐서 구현했습니다.

int LCA( int a, int b){
    
    if ( depth[a] > depth[b]){
        swap(a, b);
    }

    // 두 노드의 깊이 일치시키기
    for( int k = kmax; k >= 0; k--){
        if (pow(2, k) <= depth[b] - depth[a]){
            b = parent[k][b];
        }
    }

    if ( a == b)
        return a;

    // 최소 공통 조상 찾기
    for( int k = kmax; k >=0; k--){
        if ( parent[k][a] != parent[k][b]){
            a = parent[k][a];
            b = parent[k][b];
        }
    }

    int lca = parent[0][a];
    return lca;
}

 

이제, 함수만 호출하면 문제 해결입니다.

int M;
M = readInt();	// LCA를 구하는 문제수

for( int i = 0; i < M; i++){
    a = readInt();
    b = readInt();

    int lca = LCA(a, b);
    printf("%d\n", lca);
}

 

 

소스 코드

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

// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)

char rbuf[WBUF_SIZE];
int ridx, nidx;

inline char read() {
    if (ridx == nidx) {
        nidx = fread(rbuf, 1, 1 << 20, stdin);
        if (!nidx) return 0;
        ridx = 0;
    }
    return rbuf[ridx++];
}
inline int readInt() {
    int sum = 0;
    char now = read();
    bool flg = false;

    while (now <= 32) now = read();
    if (now == '-') flg = true, now = read();
    while (now >= 48) sum = sum * 10 + now - '0', now = read();

    return flg ? -sum : sum;
}
//----------------------------------------------------------

#define SIZE    100000
#define MAX_LEVEL  17

vector<int> graph[SIZE+1];
bool visited[SIZE+1];
int depth[SIZE+1];
int parent[MAX_LEVEL+1][SIZE+1];
int kmax;

// 너비 우선 탐색
void BFS( int start){
    
    queue<int> q;

    visited[start] = true;
    
    int next_level = 1; // 노드의 깊이
    int level_size = 1; // 현재 깊이에 있는 정점의 개수
    int cnt = 0;

    q.push(start);

    while( !q.empty()){
        int vert = q.front();
        q.pop();

        for( int x : graph[vert] ){
            if ( !visited[x] ){
                visited[x] = true;
                parent[0][x] = vert;    // 정점의 부모 노드
                depth[x] = next_level;  // 정점의 깊이
                q.push(x);
            }
        }

        cnt++;
        if ( cnt == level_size){    // 다음 깊이 단계로 진행
            cnt = 0;
            next_level++;
            level_size = q.size();
        }
    }
}

void SetupAncestor(int N){
    
    int val = 1;
    while( val <= N){
        val <<= 1;  
        kmax++;
    }

    for( int k = 1; k <= kmax; k++){
        for( int n = 1; n <= N; n++){
            parent[k][n] = parent[k-1][ parent[k-1][n] ];
        }
    }
}

int LCA( int a, int b){
    
    if ( depth[a] > depth[b]){
        swap(a, b);
    }

    for( int k = kmax; k >= 0; k--){
        if (pow(2, k) <= depth[b] - depth[a]){
            b = parent[k][b];
        }
    }

    if ( a == b)
        return a;

    for( int k = kmax; k >=0; k--){
        if ( parent[k][a] != parent[k][b]){
            a = parent[k][a];
            b = parent[k][b];
        }
    }

    int lca = parent[0][a];
    return lca;
}

int main(){

    int N;
    N = readInt();

    int a, b;
    for( int i = 1; i < N; i++){
        a = readInt();
        b = readInt();

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    BFS(1);

    SetupAncestor(N);

    int M;
    M = readInt();

    for( int i = 0; i < M; i++){
        a = readInt();
        b = readInt();

        int lca = LCA(a, b);
        printf("%d\n", lca);
    }

    return 0;
}