백준 11437번 C++ 풀이

문제

https://www.acmicpc.net/problem/11437

시간 제한	메모리 제한	solved.ac 티어
3초	256MB	골드 3

사진을 클릭하면 문제로 이동합니다.

---

풀이

 밀린 문제 정리하기. 이번엔 LCA라는 알고리즘편이다. 원래 좀 늦게 정리하려 했는데, 어제 LCA를 활용하는 문제를 푼 김에 정리해본다.

 

 LCA 알고리즘은 Lowest Common Ancestor의 약자로, 최소 공통 조상이라는 뜻이다. 사이클 없는 무방향 그래프, 즉 트리에서 임의의 두 노드의 부모 노드를 쭉 나열해보면, 어느 순간 공통된 조상을 가질 것이다. 이중에서, 가장 아래에 있는.... 그러니까 우리가 선택했던 임의의 두 노드 각각과 제일 가까운 부모 노드를 찾는 알고리즘이다. 그래서 최소의 공통된 조상을 찾는 알고리즘이다. 나중에 알고리즘들을 숙달한다면 알고리즘을 정리할때 설명하겠지만, LCA를 빠르게 찾는 테크닉이 존재한다. 하지만 이 문제는 느린 풀이로 풀 수 있다.

 

 LCA의 나이브한 알고리즘은 간단하다. 각 노드가 자신의 부모와, 본인의 높이(깊이가 좀 더 직관적으로 와닿을수도 있겠다.)를 저장한다. 임의의 루트를 지정한 후, dfs를 한번 돌리면 된다. 이제 임의의 두 노드는 두가지의 경우를 가진다. 둘의 높이가 다르거나, 같거나이다. 둘의 높이가 다르다면 똑같이 맞춰주기 위해, 더 높이 있는(더 깊이가 깊은) 노드의 높이를 다른 한쪽과 똑같아지도록 맞춰준다. 이제 높이가 같은 경우가 되었기 때문에, 두 노드의 조상이 같아질때까지 부모 노드로 이동한다. 최초로 같아지는 순간 멈추면 그것이 LCA일 것이다.

 

 트리의 높이만큼 선형시간이 걸리기 때문에 O(n)이다. 트리의 높이는 최대 n이기 때문이다. 문제는, 이를 쿼리마다 반복하기 때문에 느려질 수 밖에 없다. 이를 개선하기 위해 희소테이블을 적용하여 부모노드로 더 빠르게 이동하는 방법을 사용하는 것이 개선된 LCA 알고리즘이다.

 

 해당 문제는 전체 노드의 개수가 5만개라서 3초 안에 가능하긴하다. 원래의 풀이도 느린 풀이로 통과가 됐다. 아래는 최초에 내가 AC를 받았던 느린 LCA 코드이다.

코드-TLE

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n,m;
vector<vector<int>> tree, graph;
vector<pair<int,int>> query;

void init(int st, int p, int h){
    if(tree[st][1] != -1) return;
    tree[st][0] = p, tree[st][1] = h;
    for(int g : graph[st]) {
        init(g, st, h+1);
    }
}

void input(){
    int a, b;
    cin >> n;
    graph.resize(n + 1);
    tree.resize(n + 1, vector<int>(2, -1));
    for (int i = 1; i < n; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    cin >> m;
    query.resize(m);
    for(auto& [x, y] : query) {
        cin >> x >> y;
    }
    init(1,0,1);
}

void pull_up(int& a, int& b){
    while(tree[a][1] != tree[b][1]) a = tree[a][0];
}

void sol() {
    for(auto& [a, b] : query) {
        if (tree[a][1] > tree[b][1]) pull_up(a, b);
        else if(tree[a][1] < tree[b][1]) pull_up(b, a);
        
        while(a != b) {
            a = tree[a][0];
            b = tree[b][0];
        }
        
        cout << a << endl;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    input();
    sol();
}

 

원래는 AC를 받은 코드였지만, 정말 절묘하게도 2주정도가 흐른 후 데이터 추가로 인해 TLE로 바뀌었다. 솔직히 이때 정말 많이 헷갈렸다. 이 다음에 정리할 문제인 11438번 문제는 log(n) LCA를 사용하는 것이 맞지만, 이렇게 되면 해당 문제도 log(n)에 풀어야 하는 문제인 줄 알았다. 그러면 플래티넘 5티어인 11438번과 별 차이가 없어보였기 때문이다. 노드의 개수가 2배차이가 나지만, 둘다 log(n)의 풀이로 접근해야한다면, 의미가 없어보였기 때문이다. 

 

그래서 일단은 log(n) LCA를 적용하여 다시 풀어냈다. 사실 11438번 코드와 동일하다고 봐도 무방하다.

코드-logN

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
#define MAX_A 20

int n,m;
vector<vector<int>> tree, graph;
vector<int> depths;
vector<pair<int,int>> query;

void make_tree(int st, int p, int h) {
    tree[st][0] = p, depths[st] = h;

    for(int g : graph[st]) {
        if (g == p) continue;
        make_tree(g, st, h+1);
    }
}

void make_ancestor() {
    for (int ancestor = 1; ancestor <= MAX_A; ancestor++) {
        for (int node = 1; node <= n; node++) {
            tree[node][ancestor] = tree[tree[node][ancestor - 1]][ancestor - 1];
        }
    }
}

void init(){
    make_tree(1, 0, 1);
    make_ancestor();
}

void input(){
    int a, b;
    cin >> n;
    graph.resize(n + 1);
    tree.resize(n + 1, vector<int>(MAX_A + 1));
    depths.resize(n + 1, -1);
    for (int i = 1; i < n; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    cin >> m;
    query.resize(m);
    for(auto& [x, y] : query) {
        cin >> x >> y;
    }
    init();
}

void sol() {
    for(auto& [target, goal] : query) {
        if (depths[target] < depths[goal]){
            swap(target, goal);
        }
        int dh = depths[target] - depths[goal];
        for (int i = MAX_A; i >= 0 && dh; i--) {
            if (dh >= (1 << i)) {
                target = tree[target][i];
                dh -= (1 << i);
            }
        }

        if (target == goal){
            cout << goal << endl;
        }
        else {
            for (int i = MAX_A; i >= 0; i--) {
                if (tree[target][i] != 0 &&
                    tree[target][i] != tree[goal][i]) {
                    target = tree[target][i];
                    goal = tree[goal][i];
                }
            }
        cout << tree[goal][0] << endl;
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    input();
    sol();
}

 

 사실 이 문제는 6개월 전인 24년 8월 중순에 풀었고, 25년 3월인 지금에 와서 정리중인 문제이다. 정리하면서 다시한번 오기가 들었다. 정말 나이브한 풀이가 안되는 것일까? 사실 답은 모두 알고 있었기에, 다른 사람들의 답과 의견을 서슴없이 알아봤다. 난이도 기여를 먼저 봤다. 최근까지도 해당 문제는 나이브하게 풀 수 있다는 기여 의견이 많았다. 질문 게시판에서는 나이브한 풀이에 메모이제이션을 활용해 최적화를 시도했다고도 한다. 정 안되면 메모이제이션을 활용해보려고 했지만, 조금 더 알아보았다. 숏코딩 2등이신 분의 코드를 가독성좋게 chatGPT한테 바꿔달라고 부탁한 후, 코드를 분석해봤다. 다른 점은 딱 하나였다. 단지 내 코드는 트리의 정보를 n * 2 크기의 2차원 vector로 구성했다는 것이고, 올바른 코드는 이를 일반적인 1차원 배열 두개로 사용했다는 점이다. 그거말고는 정말 다를 것이 없었다. 그래서 내 코드의 n * 2 크기의 2차원 vector를 그냥 50001 * 2 크기의 2차원 배열로 바꿔서 다시 시도해보았다.

코드-O(N)

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n,m;
vector<vector<int>> graph;
int tree[50001][2];
vector<pair<int,int>> query;

void init(int st, int p, int h){
    if(tree[st][1]) return;
    tree[st][0] = p, tree[st][1] = h;
    for(int g : graph[st]) {
        init(g, st, h+1);
    }
}

void input(){
    int a, b;
    cin >> n;
    graph.resize(n + 1);
    for (int i = 1; i < n; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    cin >> m;
    query.resize(m);
    for(auto& [x, y] : query) {
        cin >> x >> y;
    }
    init(1,0,1);
}

void sol() {
    for(auto& [a, b] : query) {
        if (tree[a][1] < tree[b][1]) {
            swap(a, b);
        }
        while(tree[a][1] != tree[b][1]) {
            a = tree[a][0];
        }
        while(a != b) {
            a = tree[a][0];
            b = tree[b][0];
        }
        cout << a << endl;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    input();
    sol();
}

 

 AC였다... 다른 이유도 없이 단지 vector라는 이유로 틀린 것이었다. 좀 많이 허무했다. 그래도 나이브한 풀이로 통과가 가능하다는 것을 알았으니 묵은 고민이 해결되어 다행이다.