[BOJ] 백준 13325번 이진 트리 (Java)

#13325 이진 트리

난이도 : 골드 4

유형 : 트리 / DFS

13325번: 이진 트리

▸ 문제

각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 이 문제에서는, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같도록 하고, 또한 에지 가중치들의 총합을 최소화 하려고 한다.

예를 들어, 그림 1(a)에 있는 높이 2 인 포화이진트리를 살펴보자. 에지 옆에 있는 수는 그 에지의 가중치를 나타낸다. 이 경우에 대한 답이 그림 1(b)에 나타나 있다. 즉, 루트에서 모든 리프까지의 거리가 5 이고, 에지 가중치들의 총합은 이 경우에 가능한 최솟값인 15 이다. 

그림 1. 에지 가중치를 증가시키는 예.

 

포화이진트리에 들어 있는 모든 에지들의 가중치가 주어졌을 때, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같게 하면서 에지 가중치들의 총합이 최소가 되도록 하는 프로그램을 작성하시오.

▸ 입력

입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가중치는 루트에서 가까운 레벨에 있는 것부터, 같은 레벨에 있는 경우는 왼쪽부터 오른쪽의 순서로 주어진다. 각 에지의 가중치는 1 이상 1,000 이하인 정수로 주어진다.

▸ 출력

출력은 표준출력을 사용한다. 에지들의 가중치를 증가시킨 다음에 얻어지는 트리에 있는 모든 에지들의 가중치들의 총합을 한 줄에 출력한다. 어떤 에지의 가중치는 경우에 따라 1,000 이상의 값으로 증가될 수도 있다는 점에 유의하시오.

 

문제 풀이  

트리 DP 문제로 왼쪽, 오른쪽 자식 트리 중 더 큰 값을 기준으로 값을 맞춰나가주면 된다. DFS를 이용하여 재귀로 트리를 후위 순회해주면 된다. 

 

예제를 기준으로 시뮬레이션을 돌려보면 다음과 같다.

1. 리프노드 왼쪽, 오른쪽 자식 트리의 값을 더해준다. 
2. 그리고 후위순회를 하면서 res += 현재 노드 값 + abs(왼쪽 - 오른쪽)값을 더해준다. (현재 노드 값 중복되지 않게)
3. 그리고 왼쪽, 오른쪽 자식트리 중 더 큰 값을 노드 위에 올려보내주면서 재귀 탐색을 반복한다.

 

풀이 코드 

import java.io.*;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	static int n, k, res;
	static int[] arr, tree;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		k = Integer.parseInt(br.readLine());
		
		n = (int)Math.pow(2, k+1)-1;
		arr = new int[n+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=2; i<=n; i++) {
			arr[i] =Integer.parseInt(st.nextToken());
		}
		
		dfs(1,0);
		System.out.println(res);
	}
	
	static int dfs(int idx, int h) {
		if(h == k) {
			res += arr[idx];
			return arr[idx];
		}
		
		int left =  dfs(idx*2, h+1);
		int right = dfs(idx*2+1, h+1);
		res += arr[idx]+Math.abs(left -right);
		return arr[idx]+Math.max(left, right);
		
		
	}
}