BOJ)2233 사과나무

문제:icpc.me/2233

트리가 주어질 때 루트에서 DFS를 탐색하는 순서대로 0은 노드를 처음 방문할 때 1은 노드에서 더 이상 탐색이 불가능하여 return 될 때를 순서대로 수열로 나타낼 때 썩은 사과 2개를 동시에 제거 가능한 가장 가까운 노드의 0과 1의 위치를 출력하는 문제이다.

우리는 썩은 사과 2개가 주어질 때 동시에 제거 가능한 가장 가까운 노드를 LCA를 통하여 구할 수 있다.

0과 1로 이루어진 수열에서 0일 경우에는 노드를 추가하고 현재 보는 노드의 자식으로 설정 1일 경우에는 현재 보고 있는 노드의 부모를 현재 보고있는 노드로 설정해 주어 깊이와 부모를 구해준 후 LCA를 구해주면 된다.

#include <cstdio>
#include <algorithm>
#define MAX_N 2000
using namespace std;
int n, a[2 * MAX_N + 1], b[2 * MAX_N + 1], cur, par[MAX_N + 1][15], m, d[MAX_N + 1], q, w, r, f, g;
int lca(int x, int y) {
    for (int j = 1; j < 15; j++) {
        for (int i = 1; i <= n; i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    }
    if (d[x] > d[y])
        swap(x, y);
    for (int i = 14; i >= 0; i--) {
        if (d[y] - d[x] >= (1 << i))
            y = par[y][i];
    }
    if (x == y)return x;
    for (int i = 14; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= 2 * n; i++) 
        scanf("%1d", &a[i]);
    for (int i = 1; i <= 2 * n; i++) {
        if (!a[i]) {
            par[++m][0] = cur;
            d[m] = d[cur] + 1;
            cur = m;
            b[i] = m;
        }
        else {
            b[i] = cur;
            cur = par[cur][0];
        }
    }
    scanf("%d%d", &q, &w);
    r = lca(b[q], b[w]);
    for (int i = 1; i <= 2 * n; i++) {
        if (!a[i] && b[i] == r)
            g = i;
        if (a[i] && b[i] == r)
            f = i;
    }
    printf("%d %d\n", g, f);
    return 0;
}