[C++알고리즘][최소공통조상(LCA) 알고리즘]

최소 공통조상이란? 

두 노드의 조상이 처음으로 같은 경우를 최소 공통 조상이라고 한다. 지금부터 최소 공통 조상을 구하는 알고리즘을 

알아보도록 하겠다.

위와 같이 트리가 하나 있다. 여기서 1이 루트라 하고 각 깊이를 구하면 다음과 같다.

 

여기서 노드 3과 노드 8의 최소 공통 조상은 그림과 같이 노드 2인 것을 알 수 있다.

하나 더 예시를 보자면 노드 8과 노드 10의 최소 공통 조상은 노드 10인 것을 알 수 있다.

 

바로 본론으로 들어가자면 최소 공통 조상 알고리즘은 

 

1. 두 노드의 깊이를 확인한다.

2. 만약 하나가 다른 노드보다 작다면 깊이-1을 해준다.

3. 만약 깊이가 같다면 두 노드 모드 깊이 -1를 해준다.

4. 깊이-1 해주면서 만약 노드가 같아지는 지점을 찾는다.

5. 같아지는 지점이 곧 최소 공통조상이 된다.

 

위 그림과 과정을 코드로 나타내 보겠다.

 

코드

#include <iostream>
#include <vector>
#define max 100
using namespace std;
/*
입력 값
10  노드의 갯수
9   간선의 갯수
1 2
2 3
4 5
1 4
2 6
4 7
6 9
6 10
10 8
*/
vector <int> adj[max];
bool visit[max] = {false};
int depth[max]; // 깊이를 저장
int parents[max]; // 각 노드들의 부모를 저장
int V,E;
// 노드들의 깊이와 부모를 설정해주는 DFS 함수
void DFS(int node,int dep){
    visit[node] = true;
    depth[node] = dep;
    for(int i = 0;i<adj[node].size();i++){
        int next_node = adj[node][i];
        if(visit[next_node]){continue;} // 만약 방문만 정점이면 탐색x
        parents[next_node] = node; // 다음노드의 부모는 현재노드가 된다. (위에서 부터 탐색하므로)
        DFS(next_node,dep+1); // 다음노드와 깊이를 +1해준다.
    }
}
int LCA(int node_a,int node_b){
    if(node_a == node_b){return node_a;} // 만약 두 노드가 같으면 노드 반환
    if(depth[node_a] == depth[node_b]){return LCA(parents[node_a],parents[node_b]);} //두 노드의 깊이가 같을 때 
    else if(depth[node_a]>depth[node_b]){return LCA(parents[node_a],node_b);} //만약 node_a가 더 깊이가 깊을 때
    else{return LCA(node_a,parents[node_b]);} // 만약 node_b가 더 깊이가 깊을 때
}
int main(void)
{
    cin >> V >> E;
    // 인접 리스트 생성
    for(int i = 0;i<E;i++){
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    DFS(1,0); // 1이 루트이므로 1 먼저 탐색하여 깊이를 구해준다.
    cout << LCA(4,7); //노드4와 노드7의 최소 공통 조상 출력
}

추천문제

www.acmicpc.net/problem/11437

11437번: LCA