[C++] 11438번 LCA 2 - 자료 구조, 트리, 최소 공통 조상, 희소 배열

1. 문제
   • N(\(2 \leq N \leq 100,000\))개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1부터 N가지 번호가 매겨져 있으며 루트는 1이다.
   • 각 노드의 쌍 M(\(1 \leq M \leq 100,000\))개가 주어졌을 때 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력하라.
   • <입력>
     1. 노드의 개수 N
     2. 트리 상에 연결된 두 정점 (2~N)
     3. 가장 가까운 공통 조상을 알고 싶은 쌍의 개수 M
     4. 정점 쌍 (N+1+M)
   • <출력>
     • M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.
2. 문제 재정의
   • 스패닝 트리가 주어질 때 최소 공통 조상을 출력하라.
3. 해결 방법
   • 희소 배열로 부모 저장, LCA로 빠르게 탐색
4. 실수한 점, 개선한 점
   1. MAX_LOG의 크기를 가진 배열에 MAX_LOG번째 값을 건드렸는데 이차원 배열로 다음 내용이 뒤집어 씌워져 런타임 에러를 내지 않고 오류를 만들어 내서 수정했다.
   2. dfs로 탐색할 때 이미 탐색했는지를 확인하지 않아 에러가 났다.
   3. LCA에서 반환할 때 x가 아닌 x의 부모값을 반환해야 한다.
   4. cin.sync_with_stdio(0);만 썼다가 시간 초과가 났다. 아래 코드처럼 모두 다 써야 시간 초과가 나지 않는다.

 

#include <iostream>
#include <vector>

#define FOR(i, k, N) for(int i=k; i<=N; i++)

using namespace std;

const int MAX_N = 100001;
//log2(100001) = 16.xxx이므로 희소 배열을 생성할 때 16까지만 만들면 된다.
const int MAX_LOG = 18;

//정점의 개수 N, 두 노드의 쌍 M
int N, M;
//트리와 노드의 깊이
vector<int> edge[MAX_N];
int diff[MAX_N];
//희소 배열
int parent[MAX_N][MAX_LOG];

void input()
{
    cin >> N;
    
    FOR(i, 1, N-1) {
        int x, y;
        
        cin >> x >> y;
        //x와 y가 연결되어 있는 간선
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
}

//dfs를 통해 노드의 깊이 측정
void dfs(int Node)
{
    FOR(i, 0, (int)edge[Node].size()-1) {
        //만약 이미 탐색되었다면 pass
        if(diff[edge[Node][i]])
            continue;
        
        //다음 노드는 깊이가 1만큼 더 크다
        diff[edge[Node][i]] = diff[Node] + 1;
        //다음 노드의 엄마 노드는 Node이다.
        parent[edge[Node][i]][0] = Node;
        
        dfs(edge[Node][i]);
    }
}

//x와 y의 최소 공통 조상을 반환
int LCA(int x, int y)
{
    //x의 깊이가 더 크도록 한다.
    if(diff[x] < diff[y])
        swap(x, y);
    
    //x와 y의 깊이가 같도록 x의 깊이를 희소배열을 통해 줄여준다.
    for(int i=MAX_LOG-1; i>=0; i--) {
        if(diff[x] - diff[y] >= (1<<i)) {
            x = parent[x][i];
        }
    }
    
    if(x == y)
        return x;
    
    //x와 y의 깊이를 최소 공통 조상이 나타날때까지 동시에 감소시킨다.
    for(int i=MAX_LOG-1; i>=0; i--) {
        if(parent[x][i] != parent[y][i]) {
            x = parent[x][i];
            y = parent[y][i];
        }
    }
    
    return parent[x][0];
}

void solve()
{
    cin >> M;
    
    FOR(i, 1, M) {
        int x, y;
        
        cin >> x >> y;
        //x와 y의 최소 공통 조상을 출력
        cout << LCA(x, y) << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    input();
    
    diff[1]=1;
    dfs(1);
    //희소 배열 생성
    FOR(j, 1, MAX_LOG-1)
        FOR(i, 1, N)
            parent[i][j] = parent[parent[i][j-1]][j-1];
    
    solve();
    
    return 0;
}

 

 

 

 

 

 

 

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.