티스토리 뷰

알고리즘 관련/BOJ

BOJ)2233 사과나무

JASON 자손9319 2017. 2. 1. 20:35

문제:icpc.me/2233


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <algorithm>
#define MAX_N 2000
using namespace std;
int n, a[* MAX_N + 1], b[* 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] >= (<< 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 <= * n; i++
        scanf("%1d"&a[i]);
    for (int i = 1; i <= * 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 <= * 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11585 속타는 저녁 메뉴  (0) 2017.02.01
BOJ)4354 문자열 제곱  (0) 2017.02.01
BOJ)2233 사과나무  (0) 2017.02.01
BOJ)3682 동치 증명  (0) 2017.01.31
BOJ)11338 XOR Sum  (0) 2017.01.31
BOJ)2211 네트워크 복구  (0) 2017.01.26
TAG
댓글
댓글쓰기 폼