[BOJ] 백준 3038번 완전 이진 트리 (Java)

#3038 완전 이진 트리

난이도 : 플레 4

유형 : 트리 / 애드 혹

3038번: 완전 이진 트리

▸ 문제

완전 이진 트리의 각 노드는 계측적인 구조로 이루어져 있다. 루트 노드의 레벨은 0이며, 레벨 1의 두 자식 노드를 가지고 있다. 또, 레벨 1의 자식 노드의 레벨은 2이다.

보통 레벨이 N인 완전 이진 트리는 2N-1개의 노드를 가지고 있다. 레벨이 N-1이 아닌 모든 노드는 자식 노드를 두 개씩 가지고 있다.

1부터 2N-1까지 숫자를 레벨이 N인 완전 이진 트리의 각 노드에 적을 수 있다. 이때, 레벨이 D인 각각의 노드에 대해서 왼쪽 서브트리에 쓰여 있는 숫자의 합과 오른쪽 서브트리에 쓰여 있는 숫자의 합의 차이는 2D라는 조건을 만족해야 한다.

예를 들어, 루트의 왼쪽 서브 트리의 합과 오른쪽 서브 트리의 합의 차이는 1이어야 하며, 레벨이 1인 경우에는 2이어야 한다. 또, 모든 숫자는 한 번씩 사용해야 한다.

N이 주어졌을 때, 문제의 조건에 맞게 완전 이진 트리의 각 노드에 숫자를 정하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 트리의 레벨인 N이 주어진다. (1 ≤ N ≤ 15)

▸ 출력

첫째 줄에 문제의 조건에 맞게 숫자를 채운 완전 이진 트리를 프리오더로 순회한 결과를 출력한다.

 

문제 풀이  

규칙 찾아내기 문제이다. 각 루트로 부터 왼쪽, 오른쪽 서브트리의 합을 구한 후 레벨에 따른 차이를 비교해야 한다.

 

 

먼저 리프노드부터 조건에 맞춰 나가자. 이들은 서브트리가 없으므로 그들 자신하고만 비교를 하면 된다. 다음과 같이 값을 맞춰주면 리프 노드에서는 1~리프노드 갯수만큼의 수를 사용하고 각 차이가 \(2^{h-1}\)만큼 나는 것을 확인할 수 있다.

 

그럼 이제 그 위의 노드들을 채워나가면 된다. 남은 수는 \(2^{h-1}\)+1 ~\(2^{n}\)-1이다. h=3인 부분부터 살펴보면 해당 높이의 노드는 총 \(2^{h-1}\) = 4개를 갖고있고 시작 번호는 \(2^{n}\) - \(2^{h}\) + 1 로 9이다. 그래서 할당된 범위는 9 ~ 12까지임을 알 수 있다. 

 

값 할당하기

 

 각 노드에 할당되어 있는 수에 이 값을 넣어주려면 다음과 같은 식을 이용하면 된다.

• 해당 높이 노드 총 개수 - 자신의 노드 번호 + 시작번호
• 값이 1인 노드 = 4 - 1 + 9 = 12
• 값이 3인 노드 = 4 - 3 + 9 = 10
• ...
• 이렇게 모든 값을 채워주면 다음과 같은 트리를 얻는다.

 

이렇게 완성된 트리를 프리오더로 호출해주면 된다.

 

풀이 코드 

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

public class Main {

	static List<Integer>[] list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		dfs(1, 1, n);
		
	}
	
	static void dfs(int here, int h, int n) {
		if(h == n) {
			System.out.println(here);
			return;
		}
		
		int startNum = (1<<n) - (1 <<h)+1;
		int hOfnodes = (1<< (h-1));
		System.out.println(hOfnodes - here + startNum);
		
		dfs(here, h+1, n);
		dfs(here+(1<<h-1), h+1, n);
	}
}