[BOJ] 22856 - 트리 순회 (Python, JavaScript)

 

 

아이디어

 

각 노드의 자식 수를 구하되, 해당 노드가 왼쪽 서브 트리의 노드라면 1을 추가로 더한다.

 

 

풀이 #1 (Python)

 

중위 순회의 마지막 노드는 트리에서 가장 오른쪽에 있는 노드이다.

따라서 유사 중위 순회 방법에 따라 왼쪽 서브 트리에 속하는 노드는 모두 부모 노드로 이동하게 된다.

 

DFS로 왼쪽 서브 트리에 속하는 노드는 자식 수+1, 나머지 노드는 자식 수를 결과값에 더해 나간다.

 

import sys

sys.setrecursionlimit(100002)
input = sys.stdin.readline

def solution():

    def traversal(u, is_right):
        nonlocal res
        res += child[u]+1-is_right
        if tree[u][0] > 0:
            traversal(tree[u][0], 0)
        if tree[u][1] > 0:
            traversal(tree[u][1], is_right)

    N = int(input())
    tree = [[-1]*2 for _ in range(N+1)]
    child = [0]*(N+1)
    for _ in range(N):
        a, b, c = map(int, input().split())
        tree[a][0] = b
        tree[a][1] = c
        if b > 0:
            child[a] += 1
        if c > 0:
            child[a] += 1
    res = 0
    traversal(1, 1)
    print(res)

solution()

 

 

 

풀이 #2 (Python)

 

왼쪽 서브 트리에 속하지 않는 노드는 루트 노드를 제외한 모든 조상 노드가 오른쪽 서브 트리에 속해야 한다.

따라서 반복문으로 루트 노드의 오른쪽 자식 노드부터 차례로 오른쪽 자식 노드를 순회하며 그 개수를 결과값에서 뺀다.

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    res = -1
    right_child = [-1]*(N+1)
    for _ in range(N):
        a, b, c = map(int, input().split())
        res += 1
        if b > 0:
            res += 1
        if c > 0:
            res += 1
            right_child[a] = c
    u = 1
    while right_child[u] > 0:
        u = right_child[u]
        res -= 1
    print(res)

solution()

 

 

 

풀이 #3 (JavaScript)

 

풀이 #2와 마찬가지 방식으로 동작한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    const N = Number(input[0]);
    let res = -1;
    let rightChild = Array(N+1).fill(0);
    for (let i=1; i<=N; i++) {
        const [a, b, c] = input[i].split(' ').map(Number);
        res += 1;
        if (b > 0) res += 1;
        if (c > 0) {
            res += 1;
            rightChild[a] = c;
        }
    }
    let u = 1;
    while (rightChild[u] > 0) {
        u = rightChild[u];
        res -= 1;
    }
    console.log(res);
}

solution();