[BOJ / C++] 트리 순회 (트리, 애드혹)

문제링크: https://www.acmicpc.net/problem/22856

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> lc(n+1);
    vector<int> rc(n+1);
    vector<int> parent(n+1, -1);

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

        lc[a] = b;
        rc[a] = c;
        if (b != -1) parent[b] = a;
        if (c != -1) parent[c] = a;
    }

    // lastnode 찾기
    int cur = 1;
    while (rc[cur] != -1) {
        cur = rc[cur];
    }
    int lastnode = cur;

    // 이동
    vector<bool> vis(n+1, false);
    int cnt = 0;
    cur = 1;

    while (true) {
        vis[cur] = true;
        cnt++;
        if (lc[cur] != -1 && !vis[lc[cur]]) cur = lc[cur];
        else if (rc[cur] != -1 && !vis[rc[cur]]) cur = rc[cur];
        else if (cur == lastnode) break;
        else cur = parent[cur];
    }

    cout << cnt - 1;
}

 

 

2. 시간복잡도

트리를 한번 순회하므로 시간복잡도는 \(O(n) = 10^{5} < 10^{8}\) 이고 시간제한 1초내에 통과가능하다. 모든 노드를 방문했는지를 vis 배열로 판단하게 되면 순회할 때마다 노드에서 n을 또 확인해야하므로 \(O(n^{2})\)이 되므로 이런 풀이는 시간초과가 된다. lastnode를 미리 계산하고 lastnode에 도달했는지로 전체 방문여부를 판단한다.

 

 

3. 분석

위 방법처럼 직접 문제에 주어진대로 순회하면서 풀이하는 방식도 있지만 애드혹 방식으로 한번에 풀 수도 있다.

정답 = 2 * (N - 1) - depth(last_in_inorder)

 

이것은 마지막 노드에서 올라오는 것만 빼주는 원리이다. 이 때 depth(lastnode)는 lastnode에서 parent 배열을 이용해 root까지 올라오면서 depth를 측정하면된다.