백준 알고리즘 기초 - 트리

이리저리 뻗어가는 트리

어느새 기초 강의의 마지막 챕터다. 한달이 좀 덜 걸렸다. 

여기까지만 정리하고 당분간은 오픽에만 집중하고, 시험 치고 나서 중급도 시작해야겠다.

이론적인 내용의 이해가 특히 중요했던 트리 파트였다.

정리 시작!

-

* 트리 : 사이클이 없는 연결 그래프. (정점 v개, 간선 v-1개)

 - 조상, 자손 개념은 자기 자신을 포함한다.

 - 이진 트리 (binary tree) : 자식을 최대 2개만 갖는 트리. 가장 많이 사용한다.

 - 포화 (perfect) 이진 트리 : 꽉 찬 이진트리. 높이가 h이면 노드 개수 2^h - 1

 - 완전 (complete) 이진 트리 : 포화에서 가장 오른쪽에서부터 몇 개가 사라진 형태

 

* 트리 순회 : 프리오더, 인오더, 포스트오더

 - 프리오더 : 노드 -> left -> right

 - 인오더 : left -> 노드 -> right

 - 포스트오더 : left -> right -> 노드

- 트리 순회(mid) : 기본 개념으로 풀 수 있는 문제

1991번: 트리 순회

#include <iostream>
using namespace std;

typedef struct {
	int left, right;
} Node;

Node node[50];

void preorder(int x) {
	if (x == -1)
		return;
	cout << (char)(x + 'A');
	preorder(node[x].left);
	preorder(node[x].right);
}

void inorder(int x) {
	if (x == -1)
		return;
	inorder(node[x].left);
	cout << (char)(x + 'A');
	inorder(node[x].right);
}

void postorder(int x) {
	if (x == -1)
		return;
	postorder(node[x].left);
	postorder(node[x].right);
	cout << (char)(x + 'A');
}

int main()
{
	int n;
	cin >> n;
	
	char x, y, z;
	for (int i = 0; i < n; i++) {
		cin >> x >> y >> z;
		x = x - 'A';
		if (y != '.')
			node[x].left = y - 'A';
		else
			node[x].left = -1;

		if (z != '.')
			node[x].right = z - 'A';
		else
			node[x].right = -1;
	}

	preorder(0); cout << '\n';
	inorder(0); cout << '\n';
	postorder(0); cout << '\n';

	return 0;
}

- 자료형 변환에 신경 써주자.

- 트리의 높이와 너비 (mid) : 루트가 1이라는 보장은 없다!

2250번: 트리의 높이와 너비

 - 루트를 찾는 과정을 먼저 거치고, 그 다음 높이와 너비를 구한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct {
	int left, right;
	int l, w;
} Node;

Node a[10001];
vector<int> lev[10001];

int max_lev = 0;
void preorder(int x, int level) {
	if (x == -1)
		return;
	a[x].l = level;
	if (max_lev < level) max_lev = level;
	lev[level].push_back(a[x].w);
	preorder(a[x].left, level + 1);
	preorder(a[x].right, level + 1);
}

int width = 1;
void inorder(int x) {
	if (x == -1)
		return;
	inorder(a[x].left);
	a[x].w = width++;
	inorder(a[x].right);
}

int cnt[10001];

int main()
{
	int n;
	cin >> n;
	
	int x, y, z;
	for (int i = 0; i < n; i++) {
		cin >> x >> y >> z;
		a[x].left = y;
		a[x].right = z;
		if (y != -1) cnt[y] += 1;
		if (z != -1) cnt[z] += 1;
	}

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

	inorder(root);
	preorder(root, 1);

	int ans_l, ans_w = 0;
	for (int i = 1; i <= max_lev; i++) {
		int ml = n, mr = 0;
		for (int j = 0; j < lev[i].size(); j++) {
			ml = min(ml, lev[i][j]);
			mr = max(mr, lev[i][j]);
		}
		if (ans_w < mr - ml + 1) {
			ans_w = mr - ml + 1;
			ans_l = i;
		}
	}

	cout << ans_l << ' ' << ans_w << '\n';

	return 0;
}

 - 자식으로 한번도 안 쓰이면 루트다.

 - inorder로 너비를 구해주고, preorder로 높이를 구해준다.

 - 이때 높이별 너비 정보를 따로 저장해놨다가 최댓값 계산에서 써먹으면 된다. 

 

* 트리 탐색 : dfs/bfs를 이용한다. bfs로 최단 거리를 구할 수 있다.

- 트리의 부모 찾기 (low) : 백트래킹을 사용하면 된다.

11725번: 트리의 부모 찾기

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> a[100001];
bool check[100001];
int parent[100001];

int main()
{
	int n;
	cin >> n;

	int u, v;
	for (int i = 0; i < n - 1; i++) {
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}

	int pa;
	queue<int> q;
	check[1] = true;
	parent[1] = -1;
	q.push(1);

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (check[y] == false) {
				check[y] = true;
				parent[y] = x;
				q.push(y);
			}
		}
	}

	for (int i = 2; i <= n; i++)
		cout << parent[i] << '\n';

	return 0;
}

 

 

* 트리의 지름 : 트리에 존재하는 모든 경로 중에서 가장 긴 것의 길이를 트리의 지름이라고 한다.

 - 임의의 점에서 가장 긴 거리에 있는 점을 구하고, 거기서 가장 긴 거리를 구하면 그게 트리의 지름이다.

- 트리의 지름 (mid) : 위의 요령대로 코드를 구현하면 된다. 방법을 잘 기억해두자.

1167번: 트리의 지름

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

typedef struct
{
	int edge, d;
} tree;
vector<tree> t[100001];
bool check[100001];
int dist[100001];

void bfs(int x) {
	queue<int> q;
	memset(check, false, sizeof(check));
	memset(dist, 0, sizeof(dist));
	check[x] = true;
	dist[x] = 0;
	q.push(x);

	while (!q.empty()) {
		int y = q.front();
		q.pop();
		for (int i = 0; i < t[y].size(); i++) {
			int z = t[y][i].edge;
			if (check[z] == false) {
				check[z] = true;
				dist[z] = dist[y] + t[y][i].d;
				q.push(z);
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	int e;
	for (int i = 0; i < n; i++) {
		cin >> e;
		int a, d;
		cin >> a;
		while (a != -1) {
			cin >> d;
			tree tmp;
			tmp.edge = a;
			tmp.d = d;
			t[e].push_back(tmp);
			cin >> a;
		}
	}

	bfs(1);
	int start = 1;
	for (int i = 2; i <= n; i++) {
		if (dist[start] < dist[i]) {
			start = i;
		}
	}

	bfs(start);
	int ans = dist[1];
	for (int i = 2; i <= n; i++) {
		if (ans < dist[i]) {
			ans = dist[i];
		}
	}

	cout << ans << '\n';

	return 0;
}

- 코드를 어떤 식으로 구현하는지만 알면 큰 문제는 없다.

-

알고리즘 기초 강의가 끝났다. 사실상 이제 시작이다.

잘 정리해뒀다가, 종종 기초적인 개념이 흐려질 때 다시 확인해보고 해야겠다.

당분간은 오픽 시험에 집중하려고 한다. 시험이 끝나면 중급 강의에 들어간다. 차근차근 잘 해보자.

정리 끝!

기초 알고리즘도 끝!