[백준 11437번] LCA (C++)

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

11437번: LCA

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, u, v;
int parent[50001];
int depth[50001];
vector<int>node[50001];

void dfs(int n, int p) 
{
    parent[n] = p; //부모 표시
    depth[n] = depth[p] + 1; //깊이 저장 (자식은 부모 + 1)
    for(int i=0; i<node[n].size(); i++)
    {
        if(node[n][i]==p) continue; //부모로 돌아가면 스킵
        dfs(node[n][i], n); //자식과 부모
    }
}

int LCA(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v); //더 깊은 깊이를 기준으로

    while(depth[u]!=depth[v]) v=parent[v]; //깊이를 같게 만들기

    while(u!=v) //가리키는 정점이 같아질 때까지 위로 올라가기
    {
        u=parent[u];
        v=parent[v];
    }
    return v; //LCA 리턴
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N-1; i++)
    {
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }

    dfs(1, 0); //루트는 1

    cin >> M;
    while(M--)
    {
        cin >> u >> v;
        cout << LCA(u, v) <<"\n";
    }
}

최소 공통 조상을 찾는 LCA 알고리즘을 사용하는 문제이다.

LCA 알고리즘을 제대로 접하는 것은 처음이었으므로 여러 검색을 통해 알아보고 풀이를 진행하였다.

 

기본적인 틀은 입력받은 노드 값을 기준으로 트리를 먼저 만들어주고, 이후 LCA 알고리즘을 사용하는 것이다.

트리를 만들어주는 방법은 검색해보니 여러가지가 있었는데 주로 dfs, bfs를 사용하여 트리를 만들어줬다.

 

나는 dfs를 이용한 코드가 더 직관적이라고 생각하여 dfs를 사용했다.

처음 루트를 기준으로 루트의 부모는 없으니(0) dfs(1, 0)으로 시작한다.

입력받은 루트를 기준으로 부모 표시 및 부모 기준 + 1을 통해 깊이도 저장해준다.

 

이후 시작값(부모) 기준으로 연결된 값들을(자식) 체크해주며, 연결된 값이 현재 부모인 p를 가르키게 된다면 다시 돌아오는 것이므로 이 경우 스킵하도록 해준다.

이후 dfs에 연결된 값(자식) 기준으로 자식과 부모를 같이 넘겨주고 이를 토대로 parent 배열의 부모 표시 및 depth 배열의 깊이 저장에 사용한다.

 

LCA의 경우 먼저 깊이를 같게 만들기 위해 입력받은 간선 u, v의 깊이 중 더 깊은 것을 기준으로 삼는다.

이후 해당 깊이를 기준으로 u, v의 깊이를 같게 만들어주고 깊이가 같을 때를 기준으로 서로가 가르키는 정점이 같아질 때까지 조상 노드를 계속하여 탐색해준다.

같아진다면 해당 조상 노드를 반환시켜준다. (u or v)

 

만약 깊이가 다를 때 동시에 거슬러 올라간다면, 공통 조상이지만 동시에 도착하지 않아 한쪽이 지나쳐버리는 경우가 발생할 수 있다.