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

문제

 

 

접근 방식

문제 이름 그대로 트리의 높이와 넓이를 구해야 하는데

주의해야 할 점은 이진 트리가 주어질 때 루트 노드는 주어지지 않기 때문에

탐색을 무조건 1번 정점에서 시작하는 것이 아니라

따로 루트 노드를 찾아서 시작해줘야 한다.

 

트리의 높이야 탐색을 하면서 자식 노드를 방문할 때마다

부모 노드의 높이 + 1을 해주면 되니 쉽게 구할 수 있지만

문제는 트리의 넓이를 구하는 것이다.

 

 

위의 트리의 경우를 살펴보면 알 수 있는게 가로 한 줄에는

하나의 정점만 존재할 수 있고, 가장 왼쪽 가로줄의 정점부터 1번째

가장 오른쪽의 정점을 n번째로 방문한다.

 

즉, 처음 방문하는 정점은 8번 정점일 것이고

가장 마지막에 방문하는 정점은 7번 정점이 된다.

 

이진 트리가 주어지니 전위, 중위, 후위 순회 중에서 문제에 적합한

방법을 선택해서 탐색하면서 각 계층마다 처음 방문 하는 곳과

가장 나중에 방문하는 곳들을 기록해두기만 하면 된다.

 

이 문제는 왼쪽부터 가장 처음 탐색하고 중간, 오른쪽 순으로

탐색해야 하기 때문에 중위 순회가 가장 적합하다.

 

탐색하면서 기록을 하기 위해 계층별로 길이가 2인 2차원 배열에

처음 방문한 경우의 순서와 마지막에 방문한 경우의 순서를 저장하고

탐색이 끝나면 해당 배열을 사용해 이 둘을 뺀 값이 가장 큰 경우가

가장 넓은 구간을 구하는 방법이다. 

 

풀이

public class Main {

	private static int idx = 1;
	private static int height;
	private static int[] p, lc, rc;
	private static int[][] width;

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

		int n = Integer.parseInt(br.readLine());
		int c, l, r;

		p = new int[n + 1];
		lc = new int[n + 1];
		rc = new int[n + 1];
		width = new int[n + 1][2];

		Arrays.fill(p, -1);

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			c = Integer.parseInt(st.nextToken());
			l = Integer.parseInt(st.nextToken());
			r = Integer.parseInt(st.nextToken());

			lc[c] = l;
			rc[c] = r;
			if (l != -1) p[l] = c;
			if (r != -1) p[r] = c;
		}

		int root = 0;

		for (int i = 1; i <= n; i++) {
			if (p[i] == -1) {
				root = i;
				break;
			}
		}

		in(root, 1);

		int maxDepth = 1;
		int maxWidth = 1;

		for (int i = 2; i <= height; i++) {
			int mw = Math.abs(width[i][0] - width[i][1]) + 1;
			if (width[i][0] * width[i][1] == 0) mw = 1;
			if (mw > maxWidth) {
				maxDepth = i;
				maxWidth = mw;
			}
		}

		System.out.println(maxDepth + " " + maxWidth);
	}

	private static void in(int cur, int d) {
		if (lc[cur] != -1) in(lc[cur], d + 1);
		height = Math.max(d, height);
		if (width[d][0] == 0) width[d][0] = idx++;
		else width[d][1] = idx++;
		if (rc[cur] != -1) in(rc[cur], d + 1);
	}
}