[백준, Java] 9934번 : 완전 이진 트리

🔗 문제 링크

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

😮 문제 해결 방법

상근이가 도시를 방문한 조건을 살펴보면 가장 왼쪽에 있는 도시까지 방문한 후 그 부모를 방문 한 뒤 다시 오른쪽을 탐색한다.

즉, inorder 중위 순회 방식과 동일하다.

상근이가 방문한 도시의 트리 모양을 표현해줘야 하는 것이 목적이므로, 노드 번호가 1, 2, 3 순차적으로 증가하는 완전 이진 트리를 새로 만들어줬다.

새로 만든 트리를 이용해 중위 순회를 한 후 방문한 도시들을 스택에 저장한다.

입력으로 받은 도시와 스택에 저장한 도시가 동일한 순서이기 때문에 입력으로 받은 도시와 스택에 저장한 도시를 하나의 클래스로 매핑해준 뒤 새로 만든 트리의 모양대로 만들어준다.

새로 만든 트리는 노드 번호가 순차적으로 증가하는 완전 이진 트리이므로 새로 만든 객체를 노드 번호 순으로 오름차순 정렬 해준 후 매핑 된 입력으로 들어온 노드를 레벨 순으로 출력해준다.

 

1. 노드 번호가 1,2,3 … 순차적으로 증가하는 완전 이진 트리를 생성한다.
2. 새로 만든 트리를 이용해 중위 순회를 한 방문 도시 Path를 만들어 준다.
3. 입력으로 들어온 방문 도시와 새롭게 만든 트리의 방문 도시는 동일한 순서임을 보장하기 때문에 서로 하나의 클래스로 매핑해준다.
4. 하나의 클래스를 새로 만든 트리의 노드 번호 기준으로 오름차순 정렬해준다.
5. 새로 만든 트리의 1번 노드 부터 차례로 매핑된 입력으로 들어온 방문 도시를 레벨 순으로 출력해준다.

🚩 Java 코드

package com.algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_9934_완전_이진_트리 {
    static class Node {
        private int node;
        private int left;
        private int right;

        public Node(int node, int left, int right) {
            this.node = node;
            this.left = left;
            this.right = right;
        }

        public int getNode() {
            return node;
        }

        public int getLeft() {
            return left;
        }

        public int getRight() {
            return right;
        }

        public void setNode(int node) {
            this.node = node;
        }

        public void setLeft(int left) {
            this.left = left;
        }

        public void setRight(int right) {
            this.right = right;
        }
    }

    static class City implements Comparable<City> {
        private int inputPath;
        private int makePath;

        public City(int inputPath, int makePath) {
            this.inputPath = inputPath;
            this.makePath = makePath;
        }

        public int getInputPath() {
            return inputPath;
        }

        @Override
        public int compareTo(City o) {
            return Integer.compare(this.makePath, o.makePath);
        }
    }
    
    private static Stack<Integer> path, makePath;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        path = new Stack<>();
        makePath = new Stack<>();

        int N = Integer.parseInt(br.readLine());

        // 이진 트리 초기화
        Map<Integer, Node> tree = new HashMap<>();
        for (int node = 1; node < (int) Math.pow(2, N); node++) {
            tree.put(node, new Node(node, 0, 0));
        }

        // 상근이가 방문한 도시 번호 저장
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int loop = 1; loop < (int) Math.pow(2, N); loop++) {
            path.push(Integer.parseInt(st.nextToken()));
        }

        // 루트를 1 2 3 순으로 시작하는 완전 이진트리 만들기
        for(int level = 1; level < N; level++) {
            for(int node = (int) Math.pow(2, level); node < (int) Math.pow(2, level+1); node++) {
                if(node % 2 == 0) tree.get(node / 2).setLeft(node);
                else tree.get(node / 2).setRight(node);
            }
        }

        // 새로 만든 이진트리를 이용해 방문 조건(inorder)에 따라 길 만들기
        inorder(1, tree);

        // 상근이의 도시 출력
        makeCity(N);
        br.close();
    }

    private static void makeCity(int n) {
        List<City> city = new ArrayList<>();
        // 1 2 3 순서의 이진 트리로 만든 경로와 입력으로 주어진 도시 경로를 하나의 클래스로 저장
        while(!path.isEmpty() && !makePath.isEmpty()) {
            city.add(new City(path.pop(), makePath.pop()));
        }

        // 새로 만든 트리가 1 2 3 순서로 되도록 정렬 후 출력
        Collections.sort(city);
        int index = 1;
        int level = 1;
        for (City c : city) {

            System.out.print(c.getInputPath()+" ");
            if(index == (int) Math.pow(2, level)-1) {
                System.out.println();
                level++;
            }
            index++;
        }
    }

    private static void inorder(int node, Map<Integer, Node> tree) {
        if(node == 0) return;

        inorder(tree.get(node).getLeft(), tree);
        makePath.push(node);
        inorder(tree.get(node).getRight(), tree);
    }
}