[백준] 2250 트리의 높이와 너비

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

2250번: 트리의 높이와 너비

---

각 트리 노드의 열 번호를 구하고, 레벨에 따라 저장한다. 그 후 레벨에 따라 열 번호의 최소, 최대 값을 구해 연산하면 전체 트리의 최대 너비를 구할 수 있다.

 

레벨에 따라 트리 노드의 열 번호를 저장 해야하기 때문에 Map 자료 구조를 사용해야한다.

 

그리고 아래 제시된 그림을 보면, 각 노드의 열 번호가 중위 순회에 따라 부여된다는 것을 알 수 있다. 따라서 트리를 중위 순회하고 순회 순서에 따라 열 번호를 저장한다.

Python

	from sys import stdin
	import collections
	readline = stdin.readline
	N = int(readline())
	tree = collections.defaultdict(list)
	cols = collections.defaultdict(list) # 열 번호 저장
	children = set() # 루트 노드를 구하기 위해 자식 노드를 저장한다.
	for _ in range(N):
	u, v, w = map(int, readline().split())
	tree[u] = [v, w]
	children.add(v)
	children.add(w)
	def solve():
	root = find_root()
	find_col_level(root, 1)
	result = [0, 0] # 0: level, 1: width
	for level in sorted(cols):
	width = max(cols[level]) - min(cols[level]) + 1
	if result[1] < width:
	result = [level, width]
	print(*result)
	# 중위 순회
	col = 1
	def find_col_level(node, level):
	global col
	if node == -1:
	return
	find_col_level(tree[node][0], level+1)
	cols[level].append(col)
	col += 1
	find_col_level(tree[node][1], level+1)
	def find_root():
	root = 1
	for i in range(1, N+1):
	if i not in children:
	root = i
	break
	return root
	solve()

view raw BOJ2250.py hosted with ❤ by GitHub

Java

	import java.util.*;
	import java.io.*;
	public class BOJ2250 {
	static int N;
	static int[][] tree;
	static boolean[] isChild;
	public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	N = Integer.parseInt(br.readLine());
	tree = new int[N+1][2];
	isChild = new boolean[N+1];
	HashMap<Integer, ArrayList<Integer>> cols = new HashMap<>();
	for (int i=0;i<N;i++) {
	String[] line = br.readLine().split(" ");
	int u = Integer.parseInt(line[0]);
	int v = Integer.parseInt(line[1]);
	int w = Integer.parseInt(line[2]);
	tree[u][0] = v;
	tree[u][1] = w;
	cols.put(u, new ArrayList<>());
	if (v >= 0)
	isChild[v] = true;
	if (w >= 0)
	isChild[w] = true;
	}
	int root = findRoot();
	findColForLevel(root, cols, 1);
	int[] result = {0, -1};
	for (int i=1;i<=N;i++) {
	if (cols.containsKey(i)) {
	ArrayList<Integer> value = cols.get(i);
	if (value.isEmpty()) continue;
	Collections.sort(value);
	int width = value.get(value.size()-1) - value.get(0) + 1;
	if (width > result[1]) {
	result[0] = i;
	result[1] = width;
	}
	}
	}
	System.out.println(result[0] + " " + result[1]);
	}
	static int col = 1;
	public static void findColForLevel(int node, HashMap<Integer, ArrayList<Integer>> cols, int level) {
	if (node == -1)
	return;
	findColForLevel(tree[node][0], cols, level+1);
	cols.get(level).add(col++);
	findColForLevel(tree[node][1], cols, level+1);
	}
	public static int findRoot() {
	int root = 1;
	for(int i=1;i<isChild.length;i++) {
	if (!isChild[i]){
	root = i;
	break;
	}
	}
	return root;
	}
	}

view raw BOJ2250.java hosted with ❤ by GitHub