[백준] 13116번 30번 (C++)

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

 

 

이 문제는 트리가 주어지며 각각의 노드에 대해서 가장 가까운 부모를 찾아 10을 곱한값을 출력하는 문제이다.

 

따라서 이 문제는 LCA(최소공통조상)을 찾는 문제라고 볼 수 있다.

 

이 문제를 해결하기 위해서는 dfs를 사용하여 루트에서부터 각각의 노드의 부모, 깊이를 기록하여 

두 노드의 깊이를 맞춰준후 부모를 호출하여 같은 부모일 경우 최소 공통 조상이기 때문에

그 값을 10을 곱하여 출력하면 되면 해결할 수 있다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int T;
int parent[1026];
int depth[1026];

void dfs(int Node, int par, int dep) {
    if(Node >= 1024) return;
    parent[Node] = par;
    depth[Node] = dep;

    dfs(Node * 2, Node, dep+1);
    dfs(Node * 2 + 1, Node, dep+1);
}

void solve() {
    dfs(1, 0, 0);

    for(int i = 0; i < T; i++) {
        int a, b;
        cin >> a >> b;

        int deepa = depth[a];
        int deepb = depth[b];

        while(deepa > deepb) {
            a = parent[a];
            deepa--;
        }

        while(deepa < deepb) {
            b = parent[b];
            deepb--;
        }

        while(a != b) {
            a = parent[a];
            b = parent[b];
        }

        cout << a * 10<< endl;
    }
}

void input() {
    cin >> T;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

가장 핵심인 dfs함수를 살펴보면

void dfs(int Node, int par, int dep) {
    if(Node >= 1024) return;
    parent[Node] = par;
    depth[Node] = dep;

    dfs(Node * 2, Node, dep+1);
    dfs(Node * 2 + 1, Node, dep+1);
}

 

현재 노드에서 부모노드를 기록하고 왼쪽 노드와 오른쪽 노드를 다시 호출하여 탐색한다.

이때 수의 범위가 1024 까지기 때문에 1024를 넘기는 경우 return하여 함수를 종료한다.

 

void solve() {
    dfs(1, 0, 0);

    for(int i = 0; i < T; i++) {
        int a, b;
        cin >> a >> b;

        int deepa = depth[a];
        int deepb = depth[b];

        while(deepa > deepb) {
            a = parent[a];
            deepa--;
        }

        while(deepa < deepb) {
            b = parent[b];
            deepb--;
        }

        while(a != b) {
            a = parent[a];
            b = parent[b];
        }

        cout << a * 10<< endl;
    }

 

solve함수 에서는 각각의 기록된 값들에 대해서

깊이를 맞춰준다. 이때 깊이가 다른 경우 더 낮은 깊이로 맞춰 준후 부모를 호출하여 같아질때 10을 곱하여 출력하면 된다.