[종만북] 21장 트리의 구현과 순회✍

⋆｡♡ﾟ☁︎ ⋆｡선주 ﾟ☁︎ ﾟ｡♡⋆｡·2022년 1월 15일
작성 중종만북
0

알고리즘 문제 해결 전략

목록 보기
9/13
post-thumbnail

종만북 21장 트리의 구현과 순회

이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.

➖ 21-08-02

도입

  • 트리(tree): 계층적 구조를 갖는 자료들을 표현하기 위한 자료 구조
    -> 추상형 자료구조로서의 트리: 어떤 개념이 다른 개념을 포함하면 두 개념을 상위-하위로 연결
    -> 탐색형 자료구조로서의 트리: 특정한 조건을 지키도록 구성하여 같은 작업을 배열/리스트보다 빠르게 수행 (ex. 이진 검색 트리)

트리의 구성 요소

  • 자료가 저장된 노드(node)들이 간선(edge)으로 연결되어 있는 자료구조

  • 노드 간에 상/하위 관계 존재
    -> 두 노드가 연결되었을 때 한 노드(parent)는 좀더 상위, 한 노드(child)는 좀 더 하위에 있어야

⚡트리 노드의 속성

  • 노드의 차수(degree):
    한 노드의 서브트리의 수
    -> 차수가 0인 노드: 리프 노드

  • 트리의 차수(degree of a tree):
    그 트리에 있는 노드의 최대 차수

  • 노드의 깊이(depth):
    어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

  • 트리의 깊이(depth of a tree):
    어떤 트리에서 가장 깊숙히 있는 노드의 깊이
    = 트리의 높이(height of a tree)

  • 노드의 레벨(level):
    루트의 레벨을 1로 정한 뒤에 정의된다
    만일 한 노드의 레벨이 l이면, 그 자식의 레벨은 l+1이 된다

  • ⚡트리의 깊이를 그 트리에 속한 노드의 최대 레벨로 정의하는 문제도 있어 정의가 다소 헷갈린다 ...

트리의 재귀적 속성

  • 트리에서 한 노드(t)와 그의 자손들을 모두 모으면 그들도 하나의 트리가 된다
    = t를 루트로 하는 서브트리(subtree)

  • 모든 트리는 루트와 루트 밑에 있는 서브트리들의 집합이다

트리의 표현

  • 각 노드를 하나의 구조체/객체로 표현하고, 이들을 서로 포인터로 연결하여 트리 구현
    -> 이때 각 노드들은 자신의 부모와 모든 자손들에 대한 포인터를 가진다
//트리의 노드를 표현하는 객체
struct TreeNode{
	string label; //저장할 자료
	TreeNode* parent; //부모 노드를 가리키는 포인터
	vector<TreeNode*> children; //자손 노드들을 가리키는 포인터
};

  • 탐색용 트리: 트리의 구조나 사용 용도가 제한되어 있음
    -> 효율성을 위해 좀더 단순한 형태의 구현 사용

  • ex. 이진 검색 트리: 왼쪽, 오른쪽 최대 두 개의 자식 노드를 가질 수 있다
    -> 자식 노드의 포인터 배열 대신 left, right 두 개의 포인터 이용

  • ex. 힙: 노드가 들어갈 수 있는 자리가 비어있는 일이 없다
    -> 배열을 이용해 트리 표현 가능

  • ex. ⚡상호 배타적 집합 구조
    -> 각 노드가 자신의 부모를 가리키는 포인터를 가지고 있을 뿐, 부모는 각 자식에 대한 정보가 없다

트리의 순회

  • 트리를 순회하며 모든 노드에 포함된 값 출력하기
void printLabels(TreeNode* root){
	//루트에 저장된 값을 출력한다
	cout << root -> label << endl;
	//각 자손을 루트로 하는 서브트리에 포함된 값들을 재귀적으로 출력
	for(int i = 0; i< root->children.size(); ++i)
		printLabels(root->children[i]);
}
  • ⚡순회를 이용해 트리의 높이 계산하기
//root를 루트로 하는 트리의 높이를 구한다
int height(TreeNode* root){
	//자손이 없는 경우 트리의 높이 = 0
	int h = 0;
    
	for(int i = 0; i< root -> children.size(); ++i)
		h = max(h, 1 + height(root->children[i]));
	return h;
}

  • 트리의 순회의 시간 복잡도: 트리의 노드 수 n 일 때 O(n)

  • 이진 트리(binary tree)의 순회
    전위 순회(preorder): 트리의 루트 방문 -> 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문
    중위 순회(inorder): 왼쪽 서브트리 방문 -> 트리의 루트 방문 -> 오른쪽 서브트리 방문
    후위 순회(postorder): 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 -> 트리의 루트 방문

트리 순회 순서 변경 (TRAVERSAL)

  • 어떤 이진 트리의 전위 순회했을 때 노드들의 방문 순서와, 중위 순회했을 때 노드들의 방문 순서가 주어진다
    이 트리를 후위 순회했을 때 노드들의 방문 순서를 구해라

  • 트리의 각 노드마다 printPostOrder() 호출됨
    printPostOrder()내부 find(), slice()의 시간 복잡도: O(n)
    -> 전체 시간 복잡도: O(n^2)

vector<int> slice(const vector<int>& v, int a, int b){
	return vector<int> (v.begin() + a, v.begin() + b);
}

void printPostOrder(const vector<int>& preorder, const vector<int>& inorder){
	//트리에 포함된 노드 수
	const int N = preorder.size();
	if(N == 0) return;
	
	//루트: 전위 순회 순서에서 가장 첫 번째
	const int root = preorder[0];
	
	//L: 중위 순회 순서에서 루트 노드의 위치 = 왼쪽 서브트리의 크기
	const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
	
	//후위 순회 순서 출력
	
	//왼쪽 서브트리 방문
	//전위 순회 순서에서 왼쪽 서브트리: 루트 노드 후(1) ~ 왼쪽 서브트리의 크기(L+1)
	//중위 순회 순서에서 왼쪽 서브트리: 처음(0) ~ 루트 노드 전(L)
	printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
	//오른쪽 서브트리 방문
	//전위 순회 순서에서 오른쪽 서브트리: 왼쪽 서브트리 후(L+1) ~ 끝(N)
	//중위 순회 순서에서 오른쪽 서브트리: 루트 노드 후(L+1) ~ 끝(N)
	printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
    //루트 방문
    cout << root << " ";
}

⚡요새 (FORTRESS)

  • 스트로고(Strawgoh) 요새는 커다란 외벽 내에 여러 개의 원형 성벽이 겹겹이 지어진 형태로 구성되어 있다
    어떤 성벽에도 문이 없어서 성벽을 지나가려면 사다리를 타고 성벽을 오르내려야 한다
    요새 내에서 서로 왕래하는 데 성벽을 가장 많이 넘어야하는 두 지점을 왕래할 때의 성벽을 넘는 횟수를 구하라

  • 입력:
    테스트 케이스의 수 C
    성벽의 수 N
    각 성벽의 위치와 크기에 대한 정보 x, y, r -> (x,y)를 중심으로 하고 반지름 r인 원형 성벽

  • 편의상 모든 성벽의 두께는 0 이라고 가정한다
    입력에 주어지는 성벽들은 서로 겹치거나 닿지 않는다
    입력에 주어지지는 첫 번째 성벽은 외벽이며, 외벽은 입력에 주어지는 모든 다른 성벽을 포함한다

  • 성벽들은 서로 닿거나 겹치지 않는다
    -> 성이 계층적 구조로 구성되어 있다
    -> 성벽들 간의 포함 괸계를 트리로 나타낼 수 있다

  • 인접한 다른 구역으로 가기 위해 성벽을 넘는 일
    = 연결된 다른 노드로 가기 위해 간선을 따라 이동하는 일

  • 두 지점을 왕래하기 위해 넘어야 하는 성벽의 개수
    = 두 노드 사이를 연결하는 간선들의 개수
    = 두 노드를 연결하는 트리 위의 경로(path)의 길이

트리에서 가장 긴 경로 찾기

  • 최장 경로 문제의 풀이: 최장 경로의 양 끝 노드는 항상 루트 혹은 잎 노드여야 한다

  • 최장 경로의 끝 점이 트리의 내부 노드(internal node)라고 가정하자
    내부 노드는 항상 두 개 이상의 간선(부모로 가는 간선, 자식으로 가는 간선)과 연결되어 있다
    따라서 내부 노드에서 경로가 끝나는 경우 연결된 간선 중 최소한 하나는 사용되지 않은 채 남아 있게 된다
    이를 이용하면 더 긴 경로를 만들 수 있기 때문에, 최장 경로의 끝 점은 트리의 내부 노드가 될 수 없다

  • 최장 경로의 길이 = max(가장 긴 루트 ~ 잎 경로의 길이, 가장 긴 잎 ~ 잎 경로의 길이)
    -> 가장 긴 루트 ~ 잎 경로의 길이: 트리의 높이
    -> 가장 긴 잎 ~ 잎 경로의 길이: 경로가 올라가다가 내려가는 지점을 최상위 노드라고 할 때, 최상위 노드의 자손을 루트로 하는 서브트리의 높이 중 가장 큰 값 두 개를 선택하여 계산한다

  • 트리에서 가장 긴 경로를 찾는 재귀 호출 알고리즘
    -> sort() 하는 데 드는 시간 O(nlgn)을 무시하면, 트리의 순회와 같기 때문에 O(n)

struct TreeNode{
	vector<TreeNode*> children;
};

//지금까지 찾은 가장 긴 잎 ~ 잎 경로의 길이
int longest;

//longest 갱신 & root를 루트로 하는 서브트리의 높이 반환
int height(TreeNode* root){
	//root의 자식을 루트로 하는 서브트리의 높이 계산
	vector<int> heights;
	for(int i = 0; i< root->children.size(); ++i)
		heights.push_back(height(root->children[i]));
	
	//자식 노드 없을 경우 높이 = 0;
	if(heights.empty()) return 0;
	
	//longest 갱신
    //max(longest, 자손을 루트로 하는 서브트리의 높이 중 가장 큰 값 두 개)
	sort(heights.begin(), heights.end());
	if(heights.size() >= 2)
		longest = max(longest, 2 + heights[heights.size() - 1] + heights[heights.size() - 2]);
	
	//트리의 높이는 서브트리 높이의 최대치 + 1
	return heights.back() + 1;
}

//두 노드 사이의 가장 긴 경로의 길이 계산
int solve(TreeNode* root){
	longest = 0;
	int h = height(root);
	
	// max(가장 긴 루트 ~ 잎 경로의 길이, 가장 긴 잎 ~ 잎 경로의 길이)
	return max(h, longest);
}

구현

  • 주어진 번호의 성벽에 포함된 구역들을 표현하는 트리를 생성한다
    -> 0번 성벽 바로 밑에 들어갈 성벽들을 찾고, 각각의 성벽을 루트로 하는 서브트리 재귀적으로 생성
//root 성벽을 루트로 하는 트리 생성
TreeNode* getTree(int root){
	TreeNode* ret = new TreeNode();
	for(int ch = 0; ch < n; ++ch){
		//ch 성벽이 root 성벽에 직접적으로 포함되어 있다면 
		//트리를 만들고 자손 목록에 추가한다
		if(isChild(root, ch))
			ret -> children.push_back(getTree(ch));
	}
	return ret;
}
  • 두 성벽이 직접적으로 포함되어 있는지 확인하는 방법:
    두 성벽 사이에 있는 성벽이 있는지 확인한다
//입력 데이터
int n,  x[100], y[100], radius[100];

int sqr(int x){
	return x * x;
}

//두 성벽 a, b의 중심점 간의 거리의 제곱 반환
int sqrdist(int a, int b){
	return sqr(y[a] - y[b]) + sqr(x[a] - x[b]);
}

//성벽 a가 성벽b를 포함하는지 확인한다
bool encloses(int a, int b){
	return (radius[a] > radius[b]) && (sqrdist(a,b) < sqr(radius[a] - radius[b]));  
}

//성벽 트리에서 parent가 child의 부모인지 확인한다
//parent는 child를 꼭 직접 포함해야 한다
bool isChild(int parent, int child){
	if(!encloses(parent, child)) return false;
	
	//parent 성벽과 child 성벽 사이에 성벽이 있는지 확인한다
	for(int i = 0; i<n; ++i){
		if(i != parent && i != child && encloses(parent, i) && encloses(i, child)) return false;
	}
	return true;
}
  • 각 노드를 방문할 때마다 isChild() 호출
    isChild()함수 시간 복잡도: O(n)
    -> 전체 트리 생성 과정의 시간 복잡도: O(n^2)

✍...

  • https://algospot.com/judge/problem/read/FORTRESS

  • 책 속 구현 그대로 코드를 작성하였으나 답이 나오지 않음
    어디가 잘못된 것인지 다시 고민해보아야겠다

  • input:
    2
    3
    5 5 15
    5 5 10
    5 5 5
    8
    21 15 20
    15 15 10
    13 12 5
    12 12 3
    19 19 2
    30 24 5
    32 10 7
    32 9 4
    answer:
    2
    5
    output:
    2
    8

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

//-----------입력 값------------

int n;
int x[101], y[101], radius[101];

//--------성벽 트리 생성--------

struct TreeNode {
	vector<TreeNode*> children;
};

int sqrtdist(int a, int b) {
	return sqrt(y[a] - y[b]) + sqrt(x[a] - x[b]);
}

bool encloses(int a, int b) {
	return (radius[a] > radius[b]) && (sqrtdist(a, b) < sqrt(radius[a] - radius[b]));
}

bool isChild(int parent, int child) {
	if (!encloses(parent, child)) return false;

	//parent 성벽과 child 성벽 사이에 성벽이 있는지 확인한다
	for (int i = 0; i < n; ++i) {
		if (i != parent && i != child && encloses(parent, i) && encloses(i, child)) 
			return false;
	}
	return true;
}

TreeNode* getTree(int root) {
	TreeNode* ret = new TreeNode();
	for (int ch = 0; ch < n; ++ch) {
		if (isChild(root, ch))
			ret->children.push_back(getTree(ch));
	}
	return ret;
}

//------트리 최장 길이 계산------

int longest;

int height(TreeNode* root) {
	//root의 자식을 루트로 하는 서브트리의 높이 계산
	vector<int> heights;
	for (int i = 0; i < root->children.size(); ++i)
		heights.push_back(height(root->children[i]));

	if (heights.empty()) return 0;

	//longest 갱신
	//max(longest, 자손을 루트로 하는 서브트리의 높이 중 가장 큰 값 두 개)
	sort(heights.begin(), heights.end());
	if (heights.size() >= 2)
		longest = max(longest, 2 + heights[heights.size() - 1] + heights[heights.size() - 2]);

	//트리의 높이는 서브트리 높이의 최대치 + 1
	return heights.back() + 1;
}

//두 노드 사이의 가장 긴 경로의 길이 계산
int solve(TreeNode* root) {
	longest = 0;
	int h = height(root);

	// max(가장 긴 루트 ~ 잎 경로의 길이, 가장 긴 잎 ~ 잎 경로의 길이)
	return max(h, longest);
}


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

	int C;
	cin >> C;
	while (C--) {
		cin >> n;
		for (int i = 0; i< n; ++i)
			cin >> x[i] >> y[i] >> radius[i];

		//0번째 성벽이 성벽 트리의 루트가 된다
		TreeNode* tree = getTree(0);

		cout << solve(tree) << "\n";

	}

	return 0;
}

📌참고자료

profile
⋆｡♡ﾟ☁︎ ⋆｡선주 ﾟ☁︎ ﾟ｡♡⋆｡
Be able to be vulnerable, in search of truth
이전 포스트

[종만북] 20장 문자열

다음 포스트

[종만북] 24장 구간 트리✍

0개의 댓글