[0x19] 트리

트리의 정의

 

무방향이면서 사이클이 없는 연결 그래프

= 연결 그래프이면서 임의의 간선을 제거하면 연결 그래프가 아니게 되는 그래프

= 임의의 두 점을 연결하는 정점이 중복해서 나오지 않는 경로가 유일한 그래프

= V개의 정점을 가지고 V-1개의 간선을 가지는 연결 그래프

= 사이클이 없는 연결 그래프이면서 임의의 간선을 추가하면 사이클이 생기는 그래프

= V개의 정점을 가지고 V-1개의 간선을 가지는 사이클이 없는 그래프

 

정점이 1개이고 간선이 없는 그래프도 트리에 속한다.

 

트리의 BFS와 DFS

 

BFS/DFS의 과정 속에서 자신의 자식 정점들을 전부 넣어주기만 하면 된다.

// 부모 배열 채우기
vector<int> adj[10];
int p[10];
void bfs(int root) {
	queue<int> q;
	q.push(root);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		for (int nxt : adj[cur]) {
			if (p[cur] == nxt) continue;
			q.push(nxt);
			p[nxt] = cur;
		}
	}
}

 

// 부모와 depth 배열 채우기
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[10];
int p[10];
int depth[10];
void bfs(int root) {
	queue<int> q;
	q.push(root);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		for (int nxt : adj[cur]) {
			if (p[cur] == nxt) continue;
			q.push(nxt);
			p[nxt] = cur;
			depth[nxt] = depth[cur] + 1;
		}
	}
}

 

DFS는 스택으로 바꿔주기만 하면 된다

 

이진 트리의 순회

 

 

레벨 순회

 

높이 순으로 방문하는 순회이다.

BFS로 구현하면 되지만 이진 트리에 맞게 현재 보는 노드의 자식만 push 할 수 있게 코드를 살짝 수정해 주어야 한다.

 

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 순으로 방문한다

 

전위 순회 (Pre-order)

 

1. 현재 정점을 방문한다
2. 왼쪽 서브트리를 전위 순회한다
3. 오른쪽 서브트리를 전위 순회한다

 

1 - 2 - 4 - 5 - 8 - 3 - 6 - 7 순으로 방문한다

DFS와 방문 순서가 동일하다. 재귀로 간단히 구현할 수 있다.

 

중위 순회 (In-order)

 

1. 왼쪽 서브트리를 중위 순회한다
2. 현재 정점을 방문한다
3. 오른쪽 서브트리를 중위 순회한다

 

4 - 2 - 5 - 8 - 1 - 6 - 3 - 7 순으로 방문한다

트리의 모양에서 가장 왼쪽에 있는 것 부터 방문한다.

만약 트리가 이진 탐색 트리였다면 자연스럽게 크기 순으로 방문하게 된다

 

후위 순회 (Post-order)

 

1. 왼쪽 서브트리를 후위 순회한다
2. 오른쪽 서브트리를 후위 순회한다
3. 현재 정점을 방문한다

 

4 - 8 - 5 - 2 - 6 - 7 - 3 - 1 순으로 방문한다.

딱히 쉽게 비유할 만한게 없다

 

연습 문제

 

11725: 트리의 부모 찾기

vector<int> tree[100001];
int p[100001];
int n;

/*
void dfs(int v)
{
	for (auto& nxt : tree[v])
	{
		if (nxt == p[v]) continue;
		p[nxt] = v;
		dfs(nxt);
	}
}
*/

void bfs(int v)
{
	queue<int> q;
	q.push(v);

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (auto& nxt : tree[cur])
		{
			if (p[cur] == nxt) continue;
			p[nxt] = cur;
			q.push(nxt);
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i < n; ++i)
	{
		int a, b;
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

	dfs(1);

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

	return 0;
}

 

dfs도 재귀방식으로 구현해두었다.

 

1991: 트리 순회

#include <bits/stdc++.h>
using namespace std;

int n;
char lc[27], rc[27];

void preorder(int p)
{
	cout << char(p + 64);
	if (lc[p] != 0) preorder(lc[p]);
	if (rc[p] != 0) preorder(rc[p]);	
}

void inorder(int p)
{
	if (lc[p] != 0) inorder(lc[p]);
	cout << char(p + 64);
	if (rc[p] != 0) inorder(rc[p]);
}

void postorder(int p)
{
	if (lc[p] != 0) postorder(lc[p]);
	if (rc[p] != 0) postorder(rc[p]);
	cout << char(p + 64);
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		char a, b, c;
		cin >> a >> b >> c;
		if (b != '.') lc[a - 64] = b - 64;
		if (c != '.') rc[a - 64] = c - 64;
	}

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

	return 0;
}

 

A=1로 관리하는게 편하다

 

기본 문제

 

4803: 트리

#include <bits/stdc++.h>
using namespace std;

int v, e;
vector<int> graph[501];
vector<bool> vis(501);

void init_graph(int& n)
{
	for (int i = 1; i <= n; ++i)
	{
		graph[i].clear();
		vis[i] = false;
	}
}

bool bfs(int& t)
{
	queue<int> q;
	q.push(t);
	vis[t] = true;
	int vc = 0, ec = 0;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		vc++;
		ec += graph[cur].size();
		for (auto& nxt : graph[cur])
		{
			if (vis[nxt]) continue;
			q.push(nxt);
			vis[nxt] = true;
		}
	}
	return vc*2 > ec;
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int idx = 1;
	while (true)
	{
		cin >> v >> e;
		if (v + e == 0) return 0;

		init_graph(v);

		while (e--)
		{
			int a, b;
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}

		int ans = 0;
		for (int i = 1; i <= v; ++i)
		{
			if (!vis[i])
			{
				if (bfs(i)) ans++;
			}
		}
		// 트리가 없으면
		if (ans == 0) cout << "Case " << idx << ": " << "No trees." << '\n';
		// 트리가 한개면
		else if (ans == 1) cout << "Case " << idx << ": " << "There is one tree." << '\n';
		// 트리가 여러개면
		else cout << "Case " << idx << ": " << "A forest of " << ans << " trees." << '\n';
		idx++;
	}

	return 0;
}

 

정석적으로 푼 문제는 아니다. 다른 사람들의 코드를 보고 이해할 필요가 있다.