트리의 개념과 이진 트리의 순회

이번 글에서는 트리 자료구조의 개념과, 가장 간단한 트리의 일종인 이진 트리의 순회에 대해 알아봅니다.

목차

1. 트리의 구현과 순회

- 트리란

- 트리의 표현

- 트리의 순회

2. 이진 트리

- 이진 트리의 개념

- 이진 트리의 순회

3. 문제풀이: 트리 기본

- BOJ 1068번: 트리 (골드 V)

- BOJ 15681번: 트리와 쿼리 (골드 V)

- BOJ 11725번: 트리의 부모 찾기 (실버 II)

- BOJ 15900번: 나무 탈출 (실버 I)

4. 문제풀이: 이진 트리의 순회

- BOJ 1991번: 트리 순회 (실버 I)

- BOJ 9934번: 완전 이진 트리 (실버 I)

- BOJ 4256번: 트리 (골드 III)

- BOJ 2263번: 트리의 순회 (골드 II)

5. 문제풀이: 간선의 가중치가 주어진 문제

- BOJ 1240번: 노드사이의 거리 (골드 V)

- BOJ 1967번: 트리의 지름 (골드 IV)

- BOJ 1167번: 트리의 지름 (골드 III)

참고한 자료

C++ 자료구조론, Horowitz 외
http://www.yes24.com/Product/Goods/2656393

C++ 자료구조론 (2판) - YES24

알고리즘 문제 해결 전략, 구종만

https://book.algospot.com/

알고리즘 문제 해결 전략

---

트리의 구현과 순회

트리란

지금까지 공부한 자료구조들(배열, 연결 리스트, 스택, 큐)은 기본적으로 모두 자료를 한 줄로 늘어놓아 배열하기 위한 것이었습니다. 그와 달리 트리(tree) 자료구조는 계층적 구조를 갖는 자료들을 표현하기 위한 것입니다. 또한 특정 조건을 지키도록 구성된 트리들은 탐색형 자료 구조로도 유용하게 쓰일 수 있습니다.

트리의 정의

트리의 정의는 다음과 같습니다.

트리의 정의
트리(tree)는 한 개 이상의 노드(node)로 이루어진 유한 집합으로서
1. 노드 중에는 루트(root)라고 하는 노드가 하나 있고
2. 나머지 노드들은 n(0 이상)개의 분리 집합* T1, ..., Tn으로 분할될 수 있다. 여기서 T1, ..., Tn은 각각 하나의 트리이며 루트의 서브트리(subtree)라고 한다.

*분리 집합(disjoint set)은 서로 연결될 수 없는 집합을 의미

 

이것은 순환적인 정의이므로, 트리의 각 원소들은 어떤 서브트리의 루트가 되며 트리를 다루는 코드들은 대개 재귀 호출을 이용해 구현이 됩니다.

트리의 구성 요소

트리의 노드는 하나의 데이터 아이템에다 이것으로부터 다른 노드로 뻗어진 가지를 합친 것입니다. 두 연결된 노드 중 상위의 것을 부모(parent), 하위의 것을 자식(children)이라고 말합니다. 부모가 같은 두 노드는 형제(sibling)라고 합니다. 부모 노드와 그 부모들을 통틀어 선조(ancestor), 자식 노드와 그 자식들을 통틀어 자손(descendant)이라고도 부릅니다.

트리와 노드의 속성

한 노드의 서브트리의 수를 그 노드의 차수(degree)라고 하고, 차수가 0인 노드는 리프(leaf) 혹은 단말 노드(terminal node)라고 합니다. 트리의 차수(degree of a tree)는 그 트리에 있는 노드의 최대 차수입니다.

 

노드의 깊이(depth)는 루트의 깊이를 0(또는 1)으로 정한 뒤, 한 노드의 깊이가 l이면 그 자식의 깊이는 l+1이 되는 식으로 정의됩니다. 트리의 높이(height)는 트리에 속한 노드의 최대 깊이로 정의됩니다.

트리의 표현

트리의 표현

트리를 표현하는 대표적인 방법은 리스트입니다. 각 노드는 데이터와 자식 노드들에 대한 포인터를 가지도록 구현할 수 있습니다. 이때 각 노드의 차수가 다를 수 있으므로 포인터 필드의 수가 가변적이도록 구현할 수도 있고, 반대로 노드의 크기를 고정시켜 구현할 수도 있습니다. 다만 다음의 보조정리에 의해 노드의 크기를 고정시킨 일반적인 구현은 공간 낭비가 많음을 알 수 있습니다.

보조정리
차수가 \(k\)인 트리의 노드 수가 \(n\)이고 각 노드가 \(k\)개의 포인터 필드를 가지면, \(nk\)개의 필드 중 \(n(k-1)+1\)개의 필드가 0이다.

 

그런데, 놀랍게도 노드 크기가 일정하면서도 공간 낭비가 적은 구현 방식도 있습니다. 각 노드마다 딱 2개의 포인터 필드를 사용하면 되는 방식입니다.

 

트리의 성질 상, 모든 노드는 '가장 왼쪽 자식'과 '가장 가까운 오른쪽 형제'를 단 하나씩만 가집니다. 이를 이용해 왼쪽 자식-오른쪽 형제(left child-right sibling) 표현을 할 수 있습니다. 즉, 각 노드마다 왼쪽 자식과 오른쪽 형제에 대한 포인터를 가지게 하는 것입니다. 그런데, 이렇게 표현한 트리의 각 노드는 차수가 2를 넘지 않게 되고 이러한 트리를 이진 트리(binary tree)라고 합니다. 여기에서 임의의 트리를 이진 트리로 바꿀 수 있음을 알 수 있습니다.

트리의 구현

트리의 간단한 구현을 살펴봅시다. 이 트리 구현은 어떠한 트리에도 (그 트리가 트리의 정의를 만족하기만 하면) 적용될 수 있으며, 따라서 프로그래밍 대회에서도 사용할 수 있습니다.

struct TreeNode {
    string data; // 저장할 자료
    TreeNode* parent; // 부모 노드를 가리키는 포인터
    vector<TreeNode*> children; // 자식 노드들을 가리키는 포인터의 배열
}

부모 노드를 가리키는 포인터 parent는 트리 노드에 필수적이지는 않지만, 많은 응용 문제에서 필요로 하기 때문에 포함시키는 것이 좋습니다.

트리의 순회

트리의 순회

트리에 포함되어 있는 데이터를 전부 순회하는 연산을 쉽게 구현하기 위해서는 트리의 재귀적 속성을 이용합니다. 트리의 루트가 주어질 때 루트를 방문한 뒤 각 서브트리를 재귀적으로 방문하는 함수를 만들면 됩니다. 구현은 다음과 같습니다.

void printData(TreeNode* root) {
    cout << root->data << endl;
    for (int i = 0; i < root->children.size(); i++) {
        printData(root->children[i]);
    }
}

트리의 순회의 시간복잡도는 \(O(n)\)입니다. printData()는 for문 내부가 한 번 수행될 때마다 한 번씩 호출되며, 이 함수는 트리의 모든 노드에 대해 한 번씩만 호출되므로 for문 내부의 전체 수행횟수가 \((노드의 개수)-1\)번이기 때문입니다.

트리의 높이 계산

루트의 각 자식들을 루트로 하는 서브트리들의 높이를 각각 재귀 호출을 통해 계산하면, 전체 트리의 높이는 그 중 최대값에 1을 더한 것이 됩니다. 따라서 다음과 같은 코드로 트리의 높이를 계산할 수 있습니다.

int height(TreeNode* root) {
    int ans = 0;
    for (int i = 0; i < root->children.size(); i++) {
        int num = 1 + height(root->children[i]);
        if (num > ans) ans = num;
    }
    return ans;
}

이진 트리

이진 트리의 개념

이진 트리의 정의

앞서 임의의 트리가 이진 트리로 바뀔 수 있음을 알아보았기에, 이진 트리의 중요성은 두말할 필요도 없을 것입니다. 실제로 이진 트리는 자주 볼 수 있는 중요한 트리 구조의 하나입니다. 이진 트리의 정의는 다음과 같습니다.

이진 트리의 정의
이진 트리(binary tree)는
1. 공백이거나
2. 루트와 왼쪽 서브트리, 오른쪽 서브트리라고 하는 두 개의 분리된 이진 트리로 구성된 노드의 유한 집합이다.

 

위 정의에 따르면 이진 트리는 앞서 정의한 트리와 달리 0개의 노드를 가질 수 있습니다.

이진 트리의 성질

이진 트리의 두 가지 성질을 먼저 살펴봅시다.

최대 노드 수
1. 이진 트리의 깊이 \(i\)인 최대 노드 수는 \(2^{i-1}\)이다.
2. 높이가 \(k\)인 이진 트리의 최대 노드 수는 \(2^k-1\)이다.

 

증명은 1.의 경우 귀납법을 이용하며, 2.는 1.을 이용해서 바로 계산할 수 있습니다.

리프 노드 수와 차수가 2인 노드 수와의 관계
공백이 아닌 모든 이진 트리 T에 대하여, \(n_0\)는 리프 노드 수, \(n_2\)는 차수가 2인 노드 수라고 하면
\[n_0=n_2+1\]이다.

 

증명

\(n_1\)을 차수 1인 노드 수, \(n\)을 총 노드 수라고 하면 \(n=n_0+n_1+n_2\)가 성립한다.

이진 트리의 가지(간선) 수를 센다면 루트 이외의 모든 노드는 부모로부터 '들어오는' 가지가 하나씩 있으므로 총 가지 수를 \(B\)라 하면 \(n=B+1\)이다. 또, 모든 가지들은 차수가 2 또는 1인 노드에서부터 나오므로 \(B=n_1+2n_2\)도 성립한다. 지금까지 나온 식을 연립하면 결론을 얻는다.

 

이번에는 포화 이진 트리와 완전 이진 트리에 대해 알아봅시다.

포화 이진 트리의 정의
높이가 \(k\)인 포화 이진 트리(full binary tree)는 높이가 \(k\)이고 노드 수가 \(2^k-1\)인 이진 트리이다.

 

즉, 포화 이진 트리는 '높이가 \(k\)인 이진 트리 중 최대 노드 수를 가지는 것'이 됩니다. 여기서 깊이 0의 루트에서부터 점차 높은 깊이의 노드에 순차적으로 번호를 붙여봅니다. 단, 동일 깊이에서는 왼쪽에서 오른쪽으로 번호를 붙입니다. 이러한 방식으로 다음 완전 이진 트리의 정의를 이해할 수 있습니다.

완전 이진 트리의 정의
완전 이진 트리(complete binary tree)는 높이가 \(k\)이고 노드 수가 \(n\)인, 그 높이의 포화 이진 트리에서 1부터 \(n\)까지의 번호를 붙인 노드들과 일대일로 일치하는 트리이다.

 

\(n\)개의 노드를 가지는 완전 이진 트리의 높이는 \(\left \lceil \log_2(n+1)\right \rceil\)가 됩니다.

*\(\left \lceil x \right \rceil\)는 \(x\)보다 작지 않은 최소의 정수를 의미

이진 트리의 표현

완전 이진 트리의 경우 위에서 설명한 '번호 할당 기법'을 사용하여 배열로 표현할 수 있지만, 다른 이진 트리에 대해서는 배열로 표현할 경우 공간 낭비가 너무 심합니다. 또 배열 표현은 트리 중간에 노드를 삽입 또는 삭제하면 많은 노드의 위치가 변경되어야 합니다. 이러한 문제는 연결 리스트에서와 같은 연결 표현으로 쉽게 해결할 수 있습니다. 연결 리스트와 비슷하게 트리의 구현에는 두 개의 클래스가 사용됩니다. 아래 코드는 두 클래스의 정의입니다.

 

template <class T>
class Tree;

template <class T>
class TreeNode
{
friend class Tree<T>;
private:
    T data;
    TreeNode<T>* parent; // 필수 아님
    TreeNode<T>* leftChild;
    TreeNode<T>* rightChild;
};

template <class T>
class Tree {
public:
    // 트리 연산들
private:
    TreeNode<T>* root;
};

이진 트리의 순회

한 노드에서 왼쪽으로 이동, 노드 방문, 오른쪽으로 이동하는 것을 각각 L, V, R로 나타내고, 왼쪽을 오른쪽보다 항상 먼저 순회하기로 한다면 세 가지의 순회 방법 즉 LVR, LRV, VLR이 가능합니다. 이를 각각 중위 순회(inorder traversal), 후위 순회(postorder traversal), 전위 순회(preorder traversal)라고 합니다.

중위 순회

중위 순회는 먼저 더 이상 진행할 수 없을 때까지 왼쪽으로 이동하여 내려간 후, 그 노드를 '방문'하고 오른쪽 자식 노드로 이동한 뒤 계속합니다. 오른쪽으로 이동할 수 없을 때는 한 노드 뒤로 되돌아갑니다.

 

중위 순회는 재귀 호출을 이용하여 매우 간단하게 구현할 수 있습니다. (코드를 보면 아시겠지만, 다른 순회도 마찬가지 방법으로 하면 간단합니다.)

template <class T>
void Tree<T>::Inorder() {
    // 이 함수는 Tree 클래스의 public 멤버
    Inorder(root);
}

template <class T>
void Tree<T>::Inorder(TreeNode<T>* currNode) {
    // 이 함수는 Tree 클래스의 private 멤버
    if (currNode) {
        Inorder(currNode->leftChild);
        cout << currNode->data << endl;
        Inorder(currNode->rightChild);
    }
}

전위 순회

전위 순회는 노드를 먼저 방문합니다. 왼쪽으로 가서 계속하고, 더 이상 계속할 수 없으면 오른쪽으로 이동하여 계속하거나, 오른쪽으로 이동해 순회를 계속할 수 있을 때까지 되돌아갑니다.

template <class T>
void Tree<T>::Preorder() {
    // 이 함수는 Tree 클래스의 public 멤버
    Preorder(root);
}

template <class T>
void Tree<T>::Preorder(TreeNode<T>* currNode) {
    // 이 함수는 Tree 클래스의 private 멤버
    if (currNode) {
        cout << currNode->data << endl;
        Preorder(currNode->leftChild);
        Preorder(currNode->rightChild);
    }
}

후위 순회

template <class T>
void Tree<T>::Postorder() {
    // 이 함수는 Tree 클래스의 public 멤버
    Postorder(root);
}

template <class T>
void Tree<T>::Postorder(TreeNode<T>* currNode) {
    // 이 함수는 Tree 클래스의 private 멤버
    if (currNode) {
        Postorder(currNode->leftChild);
        Postorder(currNode->rightChild);
        cout << currNode->data << endl;
    }
}

레벨 순서 순회

앞서 알아본 세 가지 순회 방식은 모두 (암시적으로) 스택을 필요로 합니다. 반면 큐를 필요로 하는 순회도 있는데 바로 레벨 순서 순회(level order traversal)입니다. 이 방법은 '번호 할당 기법'에 따라 노드를 방문합니다. 먼저 루트를 방문하고 그 자식들을 큐에 삽입합니다. 다음에 방문할 노드는 큐의 앞에서 얻습니다. 이를 코드로 구현하면 다음과 같습니다.

template <class T>
void Tree<T>::LevelOrder() {
    queue<TreeNode<T>*> q;
    TreeNode<T>* currNode = root;
    while (currNode) {
        cout << currNode->data << endl;
        if (currNode->leftChild) q.push(currNode->leftChild);
        if (currNode->rightChild) q.push(currNode->rightChild);
        if (q.empty()) return;
        currNode = q.front();
        q.pop();
    }
}

문제풀이: 트리 기본

BOJ 1068번: 트리 (골드 V)

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

1068번: 트리

지금까지 논의한 개념들만 익힌 뒤 바로 이 문제풀이에 들어간다면, 다양한 난관에 부딪히게 됩니다. (저도 그랬습니다.)

그 중 가장 중요한 것은 역시 트리를 어떻게 표현할 것인가? 로, 리프 노드를 쉽게 판별하기 위해서는 어떻게 구현하는 것이 효율적일까...를 고민해야 합니다.

다행히 이 문제에서는 각 노드의 부모 노드를 제시해 주었기 때문에 앞서 '트리의 구현' 부분에서 보았던 것과 유사하게 parent와 children을 얻을 수 있을 것입니다. (그렇지만 구조체는 사용하지 않습니다. 멤버를 포인터로 구현하는 것 또한 그다지 편리하지 않아 보입니다.)

트리를 어떻게든 구현했다면, 다음 단계는 루트 노드가 주어진 임의의 트리의 리프 노드 수를 판별하는 것입니다. 힌트는 재귀 호출을 이용하는 것이며, 이것을 함수로 구현하는 데 성공하고 잔실수 없이 답을 구하는 부분까지 짜면 다 온 것입니다.

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

int countLeaf(vector<vector<int>>& children, int node) {
	// base case (if node is a leaf)
	if (children[node].empty()) {
		return 1;
	}
	// else, return sum of leaves of subtrees
	int leaves = 0;
	for (int i = 0; i < children[node].size(); i++) {
		leaves += countLeaf(children, children[node][i]);
	}
	return leaves;
}

int main() {
	// using faster cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input line 1
	int N;
	cin >> N;

	// input line 2
	vector<vector<int>> children(N); // children[i] is a vector of ith node's children
	vector<int> parent(N);
	int root;
	for (int i = 0; i < N; i++) {
		int j;
		cin >> j;
		if (j >= 0) {
			children[j].push_back(i);
			parent[i] = j;
		}
		else {
			root = i;
			parent[i] = -1;
		}
	}
	
	// count leaves in the initial tree
	int leaves = countLeaf(children, root);

	// input line 3
	int D;
	cin >> D;
	if (D == root) leaves = 0;
	else {
		leaves -= countLeaf(children, D);
		if (children[parent[D]].size() == 1) leaves++;
	}

	// output
	cout << leaves << '\n';
	return 0;
}

저의 경우 리프 노드를 루트 노드에서부터 찾아내려가기 편하도록 각 노드의 children 정보를 담고 있는 vector를 만들었습니다. 다음으로 countLeaf 함수를 구현하는 부분까지 딱히 어려움이 없었으며, 마지막으로 노드 하나를 삭제했을 때 기존의 리프 노드 수에서 얼마를 빼고 더해 주어야 하는지 판단하는 것이 약간 까다롭게 느껴졌습니다. D가 삭제된 노드라고 할 때 D를 루트로 하는 서브트리가 통째로 날아가므로 D를 루트로 하는 트리의 리프 노드 수만큼을 빼 줘야 하고, 만약 D가 그 부모의 유일한 자식이었다면 D가 사라짐으로써 부모 노드 하나가 리프 노드가 되기 때문에 1을 더해 줘야 합니다.

 

개인적으로 처음 시도한 골드 티어 문제였는데 생각보다 쉽게 풀려서 기뻤습니다.

BOJ 15681번: 트리와 쿼리 (골드 V)

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

15681번: 트리와 쿼리

이 문제는 장문의 힌트(개념 설명)가 주어져 있는데, 이것이 앞으로 문제를 풀어나가는 데 아주 큰 도움이 되니 꼭 정독해 보시기를 권장드립니다.

아무래도 힌트의 pseudocode를 참고하면서 구현하게 될 텐데, connect 배열과 입력의 형태가 다르기 때문에 이를 처리해 주는 부분이 들어가야 합니다.

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

void makeTree(vector<vector<int>>& connected, vector<int>& parent, vector<vector<int>>& children, int currNode, int prevNode) {
	vector<int> adjacent = connected[currNode - 1];
	for (int i = 0; i < adjacent.size(); i++) {
		if (adjacent[i] != prevNode) {
			parent[adjacent[i] - 1] = currNode;
			children[currNode - 1].push_back(adjacent[i]);
			makeTree(connected, parent, children, adjacent[i], currNode);
		}
	}
}

void countSubtreeNodes(vector<int>& nodeCount, vector<int>& parent, vector<vector<int>>& children, int currNode) {
	vector<int> childrenVec = children[currNode - 1];
	for (int i = 0; i < childrenVec.size(); i++) {
		countSubtreeNodes(nodeCount, parent, children, childrenVec[i]);
		nodeCount[currNode - 1] += nodeCount[childrenVec[i] - 1];
	}
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input line 1
	int N, R, Q;
	cin >> N >> R >> Q;

	// input lines 2 ~ N
	vector<vector<int>> connected(N);
	for (int i = 0; i < N - 1; i++) {
		int U, V;
		cin >> U >> V;
		connected[U - 1].push_back(V);
		connected[V - 1].push_back(U);
	}

	// build a tree recursively
	vector<int> parent(N); // parent[i-1] is the parent node of node i
	parent[R - 1] = -1; // node R is the root node
	vector<vector<int>> children(N);
	makeTree(connected, parent, children, R, -1);

	// count subtree nodes recursively
	vector<int> nodeCount(N, 1); // root of a subtree is also one of its node
	countSubtreeNodes(nodeCount, parent, children, R);

	// input lines N + 1 ~ N + Q and output
	for (int i = 0; i < Q; i++) {
		int U;
		cin >> U;
		cout << nodeCount[U - 1] << '\n';
	}

	return 0;
}

저는 connected라는 이름의 vector에 각 노드와 연결된 노드를 모두 집어넣은 뒤 힌트의 makeTree와 countSubtreeNodes를 그대로 구현하여 문제를 해결하였습니다.

BOJ 11725번: 트리의 부모 찾기 (실버 II)

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

11725번: 트리의 부모 찾기

'트리와 쿼리' 문제의 힌트를 읽었다면 이 문제에서 원하는 답은 사실상 그 문제의 하위 호환이기 때문에 날로 먹을 수가 있습니다. (하지만 저는 solved.ac 문제 티어만 보고 이 문제에 먼저 도전했기에 엄청나게 시간을 많이 썼습니다.)

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

void makeTree(vector<vector<int>>& connected, vector<int>& parent, int currNode, int prevNode) {
	vector<int> adjacent = connected[currNode - 1];
	for (int i = 0; i < adjacent.size(); i++) {
		if (adjacent[i] != prevNode) {
			parent[adjacent[i] - 1] = currNode;
			makeTree(connected, parent, adjacent[i], currNode);
		}
	}
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input line 1
	int N;
	cin >> N;

	// input lines 2 ~ N
	vector<vector<int>> connected(N);
	for (int i = 0; i < N - 1; i++) {
		int U, V;
		cin >> U >> V;
		connected[U - 1].push_back(V);
		connected[V - 1].push_back(U);
	}

	// build a tree recursively
	vector<int> parent(N); // parent[i-1] is the parent node of node i
	parent[0] = -1; // node 1 is the root node
	makeTree(connected, parent, 1, -1);

	// output
	for (int i = 1; i < N; i++) {
		cout << parent[i] << '\n';
	}

	return 0;
}

보시다시피 앞선 문제를 풀었다면 식은 죽 먹기이긴 합니다.

 

이 문제가 다른 트리 문제들보다 상대적으로 낮은 난이도로 책정된 것은 '그래프 이론'과 '깊이 우선 탐색/너비 우선 탐색'을 공부하면 쉽게 해결되기 때문인 것 같습니다. 그래프 탐색 알고리즘을 쓰지 않고 트리와 관련된 개념만 사용하여 푼다면, 꽤나 도전적인 문제라고 생각됩니다. (저의 식견은 많이 좁기 때문에, 믿거나 말거나...)

BOJ 15900번: 나무 탈출 (실버 I)

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

15900번: 나무 탈출

세 문제째 입력이 간선의 두 정점 번호의 형태로 주어지고 있습니다. 이쯤 되면 트리를 표현하는 것은 거의 똑같으니까 어렵지 않죠. 다만 이번에는 '리프 노드의 깊이의 합'을 계산하는 함수를 구현하는 것이 문제입니다. 트리 문제니까 재귀 호출로 구현하면 되겠지만, 정확한 답을 내려면 생각이 좀 필요합니다.

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

void makeTree(vector<vector<int>>& connected,  vector<vector<int>>& children, int currNode, int prevNode) {
	vector<int> adjacent = connected[currNode - 1];
	for (int i = 0; i < adjacent.size(); i++) {
		if (adjacent[i] != prevNode) {
			children[currNode - 1].push_back(adjacent[i]);
			makeTree(connected, children, adjacent[i], currNode);
		}
	}
}

int computeAnswer(vector<int>& depth,  vector<vector<int>>& children, int currNode) {
	vector<int> childrenVec = children[currNode - 1];
	// if node is a leaf, its depth should be returned
	if (childrenVec.size() == 0) {
		return depth[currNode - 1];
	}
	int answer = 0;
	for (int i = 0; i < childrenVec.size(); i++) {
		depth[childrenVec[i] - 1] = depth[currNode - 1] + 1; // children's depth is bigger than parent's depth by 1
		answer += computeAnswer(depth, children, childrenVec[i]); // answer should be accumulated through all children
	}
	return answer;
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input line 1
	int N;
	cin >> N;

	// input lines 2 ~ N
	vector<vector<int>> connected(N);
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		connected[a - 1].push_back(b);
		connected[b - 1].push_back(a);
	}

	// build a tree recursively
	vector<vector<int>> children(N);
	makeTree(connected,  children, 1, -1);

	// compute the sum of depth of leaf nodes
	vector<int> depth(N);
	int answer = computeAnswer(depth, children, 1);

	// output
	if (answer % 2 == 1) cout << "Yes\n";
	else cout << "No\n";

	return 0;
}

저는 각 노드의 깊이를 depth라는 vector에 저장하도록 하고 computeAnswer 함수를 int를 반환하도록 하여 computeAnswer(1)을 호출했습니다. 이 함수는 매개변수가 리프 노드일 때는 자신의 깊이를, 그렇지 않을 때는 자식 노드들의 함수 리턴값의 합을 리턴하도록 구현했습니다. 이로써 computeAnswer(1)은 루트 노드 기준으로 모든 리프 노드의 깊이의 합을 가집니다.

문제풀이: 이진 트리의 순회

BOJ 1991번: 트리 순회 (실버 I)

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

1991번: 트리 순회

이진 트리의 세 가지 순회 방법을 구현하는 간단한 문제입니다. 문자열을 약간만 다룰 줄 알면 편해지는 문제이기도 합니다. (서로 다른 대문자가 26개이기 때문에 노드 수도 많아야 26개...)

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

void preorder(vector<pair<int, int>>& binaryTree, int currNode) {
	if (currNode < 0 || currNode > 25) return;
	cout << char(currNode + int('A'));
	preorder(binaryTree, binaryTree[currNode].first);
	preorder(binaryTree, binaryTree[currNode].second);
}

void inorder(vector<pair<int, int>>& binaryTree, int currNode) {
	if (currNode < 0 || currNode > 25) return;
	inorder(binaryTree, binaryTree[currNode].first);
	cout << char(currNode + int('A'));
	inorder(binaryTree, binaryTree[currNode].second);
}

void postorder(vector<pair<int, int>>& binaryTree, int currNode) {
	if (currNode < 0 || currNode > 25) return;
	postorder(binaryTree, binaryTree[currNode].first);
	postorder(binaryTree, binaryTree[currNode].second);
	cout << char(currNode + int('A'));
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input line 1
	int N;
	cin >> N;

	// input line 2 ~ N
	vector<pair<int, int>> binaryTree(26);
	for (int i = 0; i < N; i++) {
		char node, left, right;
		cin >> node >> left >> right;
		binaryTree[int(node - 'A')].first = int(left - 'A');
		binaryTree[int(node - 'A')].second = int(right - 'A');
	}

	// preorder traversal
	preorder(binaryTree, 0);
	cout << "\n";

	// inorder traversal
	inorder(binaryTree, 0);
	cout << "\n";

	// postorder traversal
	postorder(binaryTree, 0);
	cout << "\n";

	return 0;
}

각 순회 방법을 재귀적으로 구현했습니다. 노드의 수가 많아야 26개이므로 각 알파벳에 해당하는 노드를 전부 만드는 것이 구현하기 편하다고 생각했습니다.

BOJ 9934번: 완전 이진 트리 (실버 I)

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

9934번: 완전 이진 트리

완전 이진 트리의 중위 순회 결과를 가지고 역으로 트리를 만드는 문제입니다. 중위 순회 결과의 정가운데에 루트 노드가 있다는 성질을 활용해 봅시다.

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

void makeTree(vector<int>& tree, vector<int>& inorder, int currNode) {
	if (inorder.size() == 0) return;
	vector<int> inorderLeft = vector<int>(inorder.begin(), inorder.begin() + inorder.size() / 2);
	vector<int> inorderRight = vector<int>(inorder.begin() + inorder.size() / 2 + 1, inorder.end());
	makeTree(tree, inorderLeft, currNode * 2 + 1);
	tree[currNode] = inorder[inorder.size() / 2];
	makeTree(tree, inorderRight, currNode * 2 + 2);
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input line 1
	int N;
	cin >> N;

	// input line 2
	vector<int> inorder(pow(2, N) - 1);
	for (int i = 0; i < pow(2, N) - 1; i++) {
		cin >> inorder[i];
	}

	// construct a tree, using properties of inorder traversal
	vector<int> tree(pow(2, N) - 1);
	makeTree(tree, inorder, 0);

	// output
	int k = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < pow(2, i); j++) {
			cout << tree[k++] << " ";
		}
		cout << "\n";
	}

	return 0;
}

중위 순회 결과를 정가운데를 기준으로 왼쪽과 오른쪽으로 잘라, 재귀 호출을 통해 트리를 구성하도록 했습니다.

BOJ 4256번: 트리 (골드 III)

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

4256번: 트리

이번에는 별다른 조건이 없는 이진 트리의 전위와 중위 순회 결과가 주어지고 후위 순회 결과를 출력하는 문제입니다. 전위 순회 결과의 맨 왼쪽에 루트 노드가 있음을 알고, 중위 순회 결과에서 루트를 찾아 왼쪽과 오른쪽 서브트리로 쪼개면 문제의 실마리가 보입니다.

#include <iostream>
using namespace std;

int preorder[1000], inorder[1000];

void printPostorder(int preL, int preR, int inL, int inR) {
	const int root = preorder[preL]; // basic property of preorder traversal
	// find the root in array 'inorder'
	int rootidx = inorder[inL];
	for (int i = inL; i < inR; i++) {
		if (inorder[i] == root) {
			rootidx = i;
			break;
		}
	}
	const int sizeL = rootidx - inL;
	const int sizeR = inR - rootidx - 1;
	if (sizeL) printPostorder(preL + 1, preL + sizeL + 1, inL, inL + sizeL);
	if (sizeR) printPostorder(preR - sizeR, preR, inR - sizeR, inR);
	cout << root << " ";
}

int main() {
	// using cin, cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input line 1
	int T;
	cin >> T;

	// for each test case
	for (int t = 0; t < T; t++) {

		// input line 1
		int n;
		cin >> n;

		// input line 2
		for (int i = 0; i < n; i++) {
			cin >> preorder[i];
		}

		// input line 3
		for (int i = 0; i < n; i++) {
			cin >> inorder[i];
		}

		// print postorder result based on other traversal results
		printPostorder(0, n, 0, n);
		cout << "\n";
	}

	return 0;
}

이전 문제들에서는 풀이에 vector를 사용했지만, 계속 시간초과가 발생해서 최대 입력만큼의 크기를 가진 배열을 전역 변수로 선언해주는 방식으로 바꿨습니다. vector를 사용하면 시간초과가 생기는 이유는 vector를 쪼개서 새로운 vector를 만들고 그걸 매개변수로 전달하는 것이 시간이 오래 걸리기 때문이기도 합니다. 반면 배열에서 읽어야 하는 처음과 끝 인덱스를 전달하는 방식은 훨씬 빠릅니다.

BOJ 2263번: 트리의 순회 (골드 II)

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

2263번: 트리의 순회

중위와 후위 순회 결과를 알려주고 전위 순회 결과를 출력하는 문제입니다.

#include <iostream>
using namespace std;

int inorder[100000], postorder[100000];

void printPreorder(int inL, int inR, int postL, int postR) {
	const int root = postorder[postR - 1]; // basic property of postorder traversal
	// find the root in array 'inorder'
	int rootidx = inorder[inL];
	for (int i = inL; i < inR; i++) {
		if (inorder[i] == root) {
			rootidx = i;
			break;
		}
	}
	const int sizeL = rootidx - inL;
	const int sizeR = inR - rootidx - 1;
	cout << root << " ";
	if (sizeL) printPreorder(inL, inL + sizeL, postL, postL + sizeL);
	if (sizeR) printPreorder(inR - sizeR, inR, postR - sizeR - 1, postR - 1);
}

int main() {
	// using cin, cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input line 1
	int n;
	cin >> n;

	// input line 2
	for (int i = 0; i < n; i++) {
		cin >> inorder[i];
	}

	// input line 3
	for (int i = 0; i < n; i++) {
		cin >> postorder[i];
	}

	// print preorder result based on other traversal results
	printPreorder(0, n, 0, n);

	return 0;
}

'트리' 문제에서 몇 가지만 손대면 됩니다. 느낌 아니까~

문제풀이: 간선의 가중치가 주어진 문제

BOJ 1240번: 노드사이의 거리 (골드 V)

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

1240번: 노드사이의 거리

이 문제부터는 연결된 두 점과 함께 간선의 가중치(거리)가 입력으로 주어집니다. 가중치가 주어진 트리를 어떻게 구현할지, 그리고 임의의 노드 사이의 (최단)거리를 어떻게 구할지 고민해 봐야 하는 문제입니다.

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

int findDistance(vector<map<int, int>>& connected, int currNode, int prevNode, int goalNode) {
	if (currNode == goalNode) return 0;
	map<int, int> adjacent = connected[currNode - 1];
	for (auto& i : adjacent) {
		if (i.first != prevNode) {
			int dist = findDistance(connected, i.first, currNode, goalNode);
			if (dist >= 0) return dist + i.second;
		}
	}
	return -1;
}

int main() {
	// using cin, cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input line 1
	int N, M;
	cin >> N >> M;

	// input line 2 ~ N
	vector<map<int, int>> connected(N);
	for (int i = 0; i < N - 1; i++) {
		int A, B, L;
		cin >> A >> B >> L;
		connected[A - 1][B] = L;
		connected[B - 1][A] = L;
	}

	// query and output
	for (int i = 0; i < M; i++) {
		int root, goal;
		cin >> root >> goal;
		cout << findDistance(connected, root, -1, goal) << "\n";
	}

	return 0;
}

우선 간선과 가중치는 map으로 구현을 했습니다. 그리고 어차피 트리의 어떤 노드든 루트로 잡을 수 있기 때문에, 루트 노드에서 특정 노드까지의 거리의 최소값을 구하도록 findDistance 함수를 재귀적으로 구현했습니다. 제가 이번에 구현한 함수는 시간 복잡도가 최적이 아니지만 이 문제를 푸는 데는 충분히 빠릅니다.

다만 시간 조건이 더 빡빡한 '정점들의 거리' 문제는 통과하지 못하는 모습을 보여주었기 때문에 향후에 LCA(최소 공통 조상) 알고리즘을 다룬 후 다시 풀어보도록 하겠습니다.

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

1761번: 정점들의 거리

BOJ 1967번: 트리의 지름 (골드 IV)

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

1967번: 트리의 지름

트리에서 가장 긴 경로를 찾는 문제입니다. 루트-리프 사이의 경로 길이와 리프-리프 사이의 경로 길이 중 가장 긴 것을 택해야 한다는 사실을 안다면, 그것을 어떻게 찾을 수 있을지를 고민해야 합니다.

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

int longest;

int height(vector<map<int, int>>& children, pair<int, int> currNode) {
	int height1 = 0; // maximum subtree height
	int height2 = 0; // 2nd maximum subtree height
	map<int, int> childrenMap = children[currNode.first - 1];
	for (auto& i : childrenMap) {
		int newHeight = height(children, i);
		if (newHeight > height1) {
			height2 = height1;
			height1 = newHeight;
		}
		else if (newHeight > height2) {
			height2 = newHeight;
		}
	}
	if (height2 > 0) longest = max(longest, height1 + height2); // update longest leaf-leaf distance
	return height1 + currNode.second;
}

int main() {
	// using cin, cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input line 1
	int N;
	cin >> N;

	// input line 2 ~ N
	vector<map<int, int>> children(N);
	for (int i = 0; i < N - 1; i++) {
		int A, B, L;
		cin >> A >> B >> L;
		children[A - 1][B] = L;
	}

	// calculate
	longest = 0; // longest leaf-leaf distance
	int h = height(children, { 1, 0 }); // longest root-leaf distance
	longest = max(longest, h);

	// output
	cout << longest;

	return 0;
}

루트-리프 사이의 경로 길이의 경우 앞서 알아본 트리의 높이 계산을 가중치가 있는 문제 상황에 맞게 변형하면 됩니다. 리프-리프 사이의 경로 길이의 최대값은 최대 높이를 갖는 서브트리 두 개를 계산하면 알 수 있습니다. 이를 이용해 재귀적으로 서브트리들의 높이를 계산하면서 리프-리프 사이의 경로 길이 최대값 longest를 전역 변수로 놓고 업데이트해 가도록 구현하였습니다.

BOJ 1167번: 트리의 지름 (골드 III)

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

1167번: 트리의 지름

입력만 다르고 위 문제와 똑같...지는 않고, 부모 자식 관계가 명확하게 주어지지 않는다는 점이 다릅니다.

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int longest;

int height(const vector<map<int, int>>& connected, pair<int, int> currNode, int parent) {
	int height1 = 0; // maximum subtree height
	int height2 = 0; // 2nd maximum subtree height
	map<int, int> childrenMap = connected[currNode.first - 1];
	childrenMap.erase(parent);
	for (auto& i : childrenMap) {
		int newHeight = height(connected, i, currNode.first);
		if (newHeight > height1) {
			height2 = height1;
			height1 = newHeight;
		}
		else if (newHeight > height2) {
			height2 = newHeight;
		}
	}
	if (height2 > 0) longest = max(longest, height1 + height2); // update longest leaf-leaf distance
	return height1 + currNode.second;
}

int main() {
	// input line 1
	int N;
	scanf("%d", &N);

	// input line 2 ~ N + 1
	vector<map<int, int>> connected(N);
	for (int i = 0; i < N; i++) {
		int A, B, L;
		scanf("%d %d", &A, &B);
		while (B != -1) {
			scanf("%d", &L);
			connected[A - 1][B] = L;
			scanf("%d", &B);
		}
	}

	// calculate
	longest = 0; // longest leaf-leaf distance
	int h = height(connected, { 1, 0 }, -1); // longest root-leaf distance
	longest = max(longest, h);

	// output
	printf("%d", longest);

	return 0;
}

하지만 논리는 거의 같기 때문에 어렵지 않게 구현할 수 있을 겁니다.

---

다음 시간에는 우선순위 큐에 대해 알아보겠습니다.