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

문제

이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.

1. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
2. 한 열에는 한 노드만 존재한다.
3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.

이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.

아래 그림은 어떤 이진트리를 위의 규칙에 따라 그려 본 것이다. 첫 번째 레벨의 너비는 1, 두 번째 레벨의 너비는 13, 3번째, 4번째 레벨의 너비는 각각 18이고, 5번째 레벨의 너비는 13이며, 그리고 6번째 레벨의 너비는 12이다.

우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.

임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오

문제풀이

사용한 알고리즘 : DFS, 구현

(1) 코드 7~8

 각 노드의 왼쪽 자식, 오른쪽 자식을 pair 로 저장하였습니다.

(2) 코드 9~10

 각 노드의 부모 수를 저장하였습니다. 부모의 수가 0인 점이 루트 노드입니다.

 ( 루트 노드가 1이 아닐 수 있음에 유의하여야 합니다. )

(3) 코드 11~14

 각 노드별 깊이를 저장하고,

 각 깊이 별 가장 왼쪽 노드, 가장 오른쪽 노드를 pair 로 저장하였습니다.

(4) 코드 19~46

 루트 노드부터 DFS로 탐색을 합니다.

 각 탐색시 

    1. 현재 노드는 자신의 왼쪽 자식 전체보다 오른쪽에 있다.

    2. 오른쪽 자식은 현재 노드의 오른쪽에 있다.

 를 생각해 탐색하는 현재 노드의 위치를 정해줍니다.

 이를 통해 매 탐색마다 구하고자 하는 답을 최신화 해줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 10005;
	typedef pair<int, int> pii;
	int N, Root;
	// child[x] : x 노드의 왼쪽자식, 오른쪽 자식
	pii child[MAX];
	// indegree[x] : x 노드의 부모 수 ( 들어오는 간선 수 )
	int indegree[MAX];
	// depth[x] : x 노드의 깊이
	int depth[MAX];
	// width[k] : k 깊이의 pair< 가장 왼쪽노드 , 가장 오른쪽노드 >
	pii width[MAX];
	int ans; // 구하고자 하는 깊이
	int w; // 구하고자 하는 최대 너비
	int path(int idx, int curr) {
	int l = child[idx].first; // 왼쪽 자식
	int r = child[idx].second; // 오른쪽 자식
	// 자식들 깊이는 부모 + 1
	depth[l] = depth[idx] + 1;
	depth[r] = depth[idx] + 1;
	int cnt = 1;
	// 왼쪽 자식이 있다면
	if(l!=-1) cnt += path(l, curr); // 왼쪽에 있는 애들 수
	curr += cnt; // 시작(curr)에 왼쪽 자식들 전체를 더해야 idx의 위치
	// 오른쪽 자식이 있다면
	if (r != -1) cnt += path(r, curr); // 오른쪽에 있는 애들
	int now_d = depth[idx]; // 현재 노드 깊이
	// 깊이 별 < 가장 왼쪽 노드, 가장 오른쪽 노드 > 최신화
	width[now_d].first = min(width[now_d].first, curr);
	width[now_d].second = max(width[now_d].second, curr);
	// 이를 통해 정답 최신화
	int Wid = width[now_d].second - width[now_d].first + 1;
	if (Wid > w || (Wid==w && ans > now_d)) {
	ans = now_d;
	w = Wid;
	}
	return cnt;
	}
	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; ++i) {
	int now, l, r;
	cin >> now >> l >> r;
	child[now] = pii(l, r);
	indegree[l]++;
	indegree[r]++;
	width[i] = pii(1987654321, 0); // 초기화
	}
	for (int i = 1; i <= N; ++i)
	if (indegree[i] == 0) Root = i; // Root가 1이 아닐수도 있다는게 좀... 참...
	depth[Root] = 1;
	path(Root, 0);
	cout << ans << '\n';
	cout << w << '\n';
	return 0;
	}

view raw BOJ 2250.cpp hosted with ❤ by GitHub