백준9934 - 완전 이진 트리(Java)

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

9934번: 완전 이진 트리

재귀 문제를 풀어보았다.
문제는 길지만 정리하면 완전 이진 트리의 값이 주어지고, 이 트리를 레벨별로 출력하는 문제였다.

입력이 항상 완전 이진트리임이 보장되기 때문에, 전위 순회를 진행시키고 방문 순서대로 StringBuilder에 append하는 방식으로 풀어주었다.

 

높이가 4인 완전 이진 트리를 예시로 생각해보자

• 전체 노드의 개수는 2^4 - 1 개이다.
• 루트 노드의 인덱스는 가운데에 있는 8, 즉 2^(4-1) 이다.

그러면 루트 노드 기준으로 높이가 3인 두 개의 완전 이진 트리형태의 서브트리로 분리된다.
두 개의 서브트리는 다음과 같다.

• 전체 노드의 개수는 2^3 - 1 개이다.
• 루트 노드의 인덱스는 각각 4 / 12이다.

여기서 점화식을 도출해낼 수 있다.

높이가 n인 완전 이진트리의 경우
- 전체 노드의 개수는 2^n - 1개이다.
- 루트 노드의 인덱스는 2^(n-1) 이다.
- 서브트리의 루트 노드 인덱스는 이전 트리의 루트 노드 인덱스 +- 2^(트리 레벨과 반비례하는 값) 

자식 노드와의 인덱스가 1씩 차이날때까지 진행해주면 되는데, 트리의 총 높이와 현재 레벨(h)의 값이 같을 때까지 진행해주면 된다.

2의 n승의 경우 비트를 통해 계산하면 편하므로 다음과 같이 코드를 짜보았다.

 

package BOJ;

import java.io.*;
import java.util.*;

public class BOJ9934 {

    private static int[] arr;
    private static StringBuilder[] builders;
    private static int K;

    public static void main(String[] args) throws IOException {
        init();

        // 루트 노드 인덱스 : 1 << (K - 1)
        // 시작 높이 : 1 (최상단)
        go(K == 1 ? 1 : (1 << (K - 1)), 1);

        print();
    }

    private static void go(int n, int h) {
        if (K < h) return;
        builders[h - 1].append(arr[n]).append(" ");

        go(n - (1 << (K - h - 1)), h + 1);
        go(n + (1 << (K - h - 1)), h + 1);
    }

    private static void print() {
        for (int i = 0; i < K; i++) {
            System.out.println(builders[i].toString().trim());
        }
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        K = parse(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[1 << K];
        builders = new StringBuilder[K];
        for (int i = 0; i < K; i++) {
            builders[i] = new StringBuilder();
        }
        for (int i = 1; i < arr.length; i++) {
            arr[i] = parse(st.nextToken());
        } // end init
    }

    private static int parse(String s) {
        return Integer.parseInt(s);
    }
}