[BOJ/JAVA] 9934번: 완전 이진 트리

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

9934번: 완전 이진 트리

키워드

1. 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다.
2. 현재 빌딩의 왼쪽 자식에 있는 빌딩에 아직 들어가지 않았다면, 왼쪽 자식으로 이동한다.
3. 현재 있는 노드가 왼쪽 자식을 가지고 있지 않거나 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩을 들어가고 종이에 번호를 적는다.
4. 현재 빌딩을 이미 들어갔다 온 상태이고, 오른쪽 자식을 가지고 있는 경우에는 오른쪽 자식으로 이동한다.
5. 현재 빌딩과 왼쪽, 오른쪽 자식에 있는 빌딩을 모두 방문했다면, 부모 노드로 이동한다.

총 K개의 줄에 걸쳐서 정답을 출력한다. i번째 줄에는 레벨이 i인 빌딩의 번호를 출력한다.

---

구현

완전 이진트리임을 이용한다. → 주어지는 번호는 포화이진트리만큼 주어지므로 이를 배열의 인덱스로 이용한다.

위 이동 순서대로 해당 노드에 번호를 부여한다.

출력의 경우는

1줄에 1개

2줄에 2개

3줄에 4개

…

k 줄에 2^(k-1) 개를 출력한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class java_9934 {
    static int K;
    static int tree[];
    static Deque<Integer> queue;
    static boolean isVisited[];

    public static void trap(int thisNode) {
        if (thisNode == 0) {
            return;
        }
        // 현재 빌딩과 왼쪽, 오른쪽 자식에 있는 빌딩을 모두 방문 했다면..
        if (thisNode * 2 >= tree.length || tree[thisNode * 2] != 0) {
            if (thisNode * 2 + 1 >= tree.length || tree[thisNode * 2 + 1] != 0) {
                if (tree[thisNode] != 0) {
                    trap(thisNode / 2);
                }
            }
        }

        // 왼쪽 자식의 빌딩에 들어가지 않았다면 왼쪽 자식으로 이동
        try {
            if (tree[thisNode * 2] == 0) {
                trap(thisNode * 2);
            }
        } catch (ArrayIndexOutOfBoundsException e) {

        }

        // 왼쪽 자식을 갖고 있지 않거나, 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩 들어가기
        if (thisNode * 2 >= tree.length || tree[thisNode * 2] != 0) {
            tree[thisNode] = queue.poll();
        }

        // 현재 빌딩을 이미 갔다 온 상태이고, 오른쪽 자식을 가지는 경우 -> 오른쪽 자식으로 이동
        if (tree[thisNode] != 0) {
            if (thisNode * 2 + 1 < tree.length) {
                trap(thisNode * 2 + 1);
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 깊이가 K인 완전 이진 트리 -> 포화 이진 트리
        // 2^K-1 개의 노드 -> 1차원 배열 사용
        K = Integer.parseInt(br.readLine());

        tree = new int[(int) Math.pow(2, K)];

        queue = new ArrayDeque<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < tree.length - 1; i++) {
            queue.add(Integer.parseInt(st.nextToken()));
        }

        trap(1);

        int targetCount = 0;
        int count = 0;
        for (int i = 1; i < tree.length; i++) {
            System.out.print(tree[i] + " ");
            count++;
            if (count == Math.pow(2, targetCount)) {
                System.out.println();
                targetCount++;
                count = 0;
            }
        }

        br.close();
    }
}

---