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

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

2250번: 트리의 높이와 너비

//	1800kb	664ms
#include <cstdio>
#include <unordered_map>
#include <cstdlib>
int N;
int child[10000 + 2];
int root;
int col_cnt;
int row_cnt;
int max_len;
int depth;

struct _st
{
	int l;		// 왼쪽 
	int r;		// 오른쪽
	int row;	// 행번호
	int col;	// 열번호
};

using namespace std;

unordered_map<int, _st>Tree;	// key : 노드 data : 왼쪽, 오른쪽, 행번호, 열번호 



void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int node = 0; int left = 0; int right = 0;
		scanf("%d %d %d", &node, &left, &right);
		Tree.insert({ node, {left, right, 0, 0} });
		child[left] = 1;
		child[right] = 1;
	}
}


void get_root()
{
	for (int i = 1; i <= N; i++) {
		if (child[i] == 0) root = i;
	}
}


void in_order(int n, int row_num)
{
	auto iter = Tree.find(n);
	iter->second.row = row_num;
	row_cnt = (row_cnt < row_num) ? row_num : row_cnt;

	if (iter->second.l != -1) in_order(iter->second.l, row_num + 1);
	iter->second.col = col_cnt;
	col_cnt++;
	//printf("node : %d row_num : %d col_cnt : %d\n", n, iter->second.row, iter->second.col);
	if (iter->second.r != -1) in_order(iter->second.r, row_num + 1);
}


void get_max(void)
{
	for (auto iter1 = Tree.begin(); iter1 != Tree.end(); iter1++) {
		for (auto iter2 = Tree.begin(); iter2 != Tree.end(); iter2++) {
			if (iter1 == iter2) continue;
			if (iter1->second.row == iter2->second.row) {
				int tmp = abs(iter1->second.col - iter2->second.col);
				if (tmp > max_len) {
					depth = iter1->second.row;
					max_len = tmp;
				}
				else if (tmp == max_len) {
					if (iter1->second.row > depth) continue;
					depth = iter1->second.row;
					max_len = tmp;
				}
			}
		}
	}
}


int main()
{
	input();
	get_root();			// 루트 노드 찾기
	in_order(root, 0);	// 루트노드, 뎁스
	get_max();
	printf("%d %d\n", depth + 1, max_len + 1);
	return 0;
}
#endif

//	1632kb	4ms
#include <cstdio>
#include <unordered_map>
int N;
int P[10000 + 2];	//root노드 찾기 위함 
int col_num = 1;	//열 시작 1부터
int row_cnt;
int row_ans = 1;	//행 시작 1부터 
int max_len;

using namespace std;

struct _st
{
	int l;	// 왼쪽 자식노드 
	int r;	// 오른쪽 자식노드 
};
unordered_map<int, _st> Tree;


struct _nt
{
	int col_min;	// 뎁스별 열의 왼쪽 끝값
	int col_max;	// 뎁스별 열의 오른쪽 끝값
} depth[10000 + 2];


void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int node = 0; int left = 0; int right = 0;
		scanf("%d %d %d", &node, &left, &right);
		Tree.insert({ node, {left, right} });
		P[left] = 1;		// 자식노드이면 배열값 1로 갱신
		P[right] = 1;		// 자식노드이면 배열값 1로 갱신
	}
}

int get_root()
{
	for (int i = 1; i <= N; i++) {
		if (P[i] == 0) return i;
	}
	return -1;
}


void DFS(int n, int row)
{
	auto iter = Tree.find(n);
	row_cnt = (row > row_cnt) ? row : row_cnt;
	// 왼쪽 서브트리
	if (iter->second.l != -1) DFS(iter->second.l, row + 1);
	
	//루트
	if (depth[row].col_min == 0) {		// 전체 트리에서 처음 등장한 노드
		depth[row].col_min = depth[row].col_max = col_num;	// 열의 맨 왼쪽 값 갱신
	}
	else depth[row].col_max = col_num;	// 열의 맨 오른쪽 값 갱신
	col_num++;
	//printf("%d ", n);
	
	// 오른쪽 서브트리
	if (iter->second.r != -1) DFS(iter->second.r, row + 1);
}


void get_max()
{
	for (int d = 1; d <= row_cnt; d++) {
		int tmp = depth[d].col_max - depth[d].col_min;
		if (max_len < tmp) {
			max_len = tmp;
			row_ans = d;
		}
		if (max_len == tmp) {
			if (row_ans < d) continue;
			row_ans = d;
		}
	}
}



int main()
{
	input();
	int root = get_root();
	DFS(root, 1);	// 최상단 루트노드부터 탐색 시작, 뎁스는 1부터 
	get_max();
	printf("%d %d\n", row_ans, max_len + 1);
	return 0;
}

런타임을 줄여보기 위한,,, 갖은 노력이랄까 ,,, ? ㅋㅋㅋㅋ 

아무래도 첫 코드는 get_max 함수에서 내가 Tree를 두 번 탐색하면서 각 뎁스의 모든 열의 값들을 비교해서 664ms라는 어마어마한 시간이 나온 듯 싶다. 

이걸 두번째 코드에서 줄여보았다. 

 

 

// 변수 선언 

변수를 선언하는 과정에서 주의해야 할 점은 행과 열이 모두 1부터 시작한다는 것(col_num = 1, row_ans = 1)이다. 만약 초기값을 이렇게 설정해주지 않으면 92%에서 틀렸다고 뜬다(저기 "틀렸습니다" 중 과반수 이상의 원인이 이것ㅋ).

row_cnt는 DFS 함수 돌리면서 가장 깊은 뎁스가 어디까지인지 확인하기 위함이다. 

 

구조체 타입 _st 는 Tree를 만들기 위한 맵을 선언하는 과정에서 특정 노드의 왼쪽, 오른쪽 자식 노드를 저장하기 위해 선언했다. 사실 맵으로 안하고 구조체에 그냥 받아줘도 무방하다. 

그리고 구조체 타입 _nt는 각 뎁스별 열의 왼쪽 끝값과 오른쪽 끝값을 저장하기 위함이다. 이건 그냥 depth라는 구조체로 생성해 주었다. 

 

 

// input( ) 함수

이 문제는 최상단 루트를 친절하게 알려주지 않는다. 그래서 우리가 구해야한다. 

문제에서 "다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다" 라고 했으므로 배열 P 하나를 두고 P[오른쪽 자식노드] = 1, P[왼쪽 자식노드] = 1 이렇게 갱신해주면 P배열의 값이 0인 노드가 최상단 루트가 된다. (이건 사실 내가 생각한건 아니고 엄청 똑똑한 애가 알려줌,, 압도적 감사,,)

 

 

// get_root( ) 함수

배열 P에 자식인 노드들을 모두 1로 표시해놓았으므로 P[i] == 0이면 최상단 루트노드이다. 

 

 

// DFS( ) 함수

이 문제는 1열부터 차례대로 채워나가야 하므로 "왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리" 순으로 탐색하는 중위순회(in-order)를 사용해야 한다. 

나는 컨테이너를 맵으로 선언했기 때문에, iter 변수를 선언하고 n의 위치를 받아주었다. 

그리고 왼쪽 노드가 존재한다면(iter->second.l != -1) 왼쪽 서브트리부터 탐색하도록 한다. 탐색이 끝나면 서브트리의 루트로 오는데, 만약 해당 뎁스에서 열의 왼쪽 끝값이 0이면 각 뎁스에서 처음 등장한 노드라는 것이다. 따라서 열의 왼쪽 끝값과 오른쪽 끝값을 col_num이라고 갱신한다. 그게 아니라면 각 뎁스에서 열의 오른쪽 끝 값을 갱신해 준다(최대 너비를 구하기 위함). 

이후 오른쪽 서브트리도 동일하게 탐색한다. 

 

 

// get_max( ) 함수

DFS 함수를 돌리면서 가장 깊은 뎁스의 번호를 row_cnt에 저장해 주었다. 

따라서 N까지 돌릴필요 없이 d를 row_cnt까지 옮겨가면서 너비의 최대값을 구해준다.