[문제해결전략] Chapter 21 트리의 구현과 순회

chellchell·2020년 8월 12일

문제해결전략

목록 보기

13/17

21.5문제: 요새(ID:FORTRESS)

문제

중세의 성과 요새들은 보안을 튼튼히 하면서도 더 넓은 영역을 보호하기 위해 여러 개의 성벽을 갖고 있었다고 하지요. 전세계에서 가장 편집증이 심한 영주가 지은 스트로고(Strawgoh) 요새는 이의 극치를 보여줍니다. 이 요새는 그림과 같이 커다란 원형 외벽 내에 여러 개의 원형 성벽이 겹겹이 지어진 형태로 구성되어 있는데, 어떤 성벽에도 문이 없어서 성벽을 지나가려면 사다리를 타고 성벽을 오르내려야 합니다. 요새 내에서도 한 곳에서 다른 곳으로 이동하는 데 시간이 너무 오래 걸린다는 원성이 자자해지자, 영주는 요새 내에서 왕래가 불편한 곳들을 연결하는 터널을 만들기로 했습니다. 계획을 세우기 위해 요새 내에서 서로 왕래하기 위해 가장 성벽을 많이 넘어야 하는 두 지점을 찾으려고 합니다. 예를 들어 위 그림의 경우, 별표로 표시된 두 지점 간을 이동하기 위해서는 다섯 번이나 성벽을 넘어야 하지요.
성벽들의 정보가 주어질 때 가장 성벽을 많이 넘어야 하는 두 지점 간을 이동하기 위해 몇 번이나 성벽을 넘어야 하는지 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 100) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 성벽의 수 N (1 <= N <= 100) 이 주어집니다. 그 후 N 줄에는 각 3개의 정수로 각 성벽의 위치와 크기에 대한 정보 xi , yi , ri 가 주어집니다. (0 <= xi, yi <= 1000,1 <= ri <= 1000,0 <= i<N) 이 때 i 번 성벽은 (xi, yi) 를 중심으로 하는 반지름 ri 인 원형으로 설치되어 있습니다. 편의상 모든 성벽의 두께는 0이라고 가정하며, 입력에 주어지는 성벽들은 서로 겹치거나 닿지 않습니다. 입력에 주어지는 첫 번째 성벽은 외벽이며, 외벽은 입력에 주어지는 모든 다른 성벽을 포함합니다.

출력

각 테스트 케이스마다 한 줄에 두 지점 간 이동을 위해 최대 몇 번이나 성벽을 넘어야 하는지를 출력하세요.

예제 입력
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 
예제 출력
2
5

First Thoughts

요새와 트리

처음 이 문제를 봤을 때 트리를 이용해야되겠다는 느낌은 분명했다. 각 원들의 포함관걔를 통해 트리를 완성해야겠다. A라는 원이 B라는 원 안에 있을 때 B는 트리에서 부모 역할을 하고 A는 자식 역할을 한다. 그래서 입력을 통해 트리를 직접 만들고 트리를 만드는 과정에서 최소값과 최대값을 비교하여 포함여부를 확인하며 배치할려고 하였다. 코드를 짜다보니 점점 길이는 길어지고 예시를 적용하며 해본 결과 따로 처리해야할 부분들이 많았다. 그래서 해제 코드를 보고 풀이를 익혔다.

Answer Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//트리 구조체
struct TreeNode {
	vector <TreeNode*> children;
};
//잎-잎의 간선의 수
int longest;
//원의 개수
int n;
//중심위치와 반지름
int y[100], x[100], radius[100];
//서브트리의 높이
int height(TreeNode* root) {
	vector<int> heights;
	for (int i = 0; i < root->children.size(); i++) {
		//root의 자식을 최상위 노드로 하는 트리의 높이
		heights.push_back(height(root->children[i]));
	}
	//자식이 없다면 0 반환
	if (heights.empty())
		return 0;
	//크기 순으로 정렬
	sort(heights.begin(), heights.end());
	//자식이 2개 이상일 경우
	if (heights.size() >= 2) {
		//2번째로 큰 높이와 1번째로 큰 높이(longest를 비교, 반환X)
		longest = max(longest, 2 + heights[heights.size() - 2] + heights[heights.size() - 1]);
	}
	//트리의 높이는 가장 큰 서브트리 높이의 1을 더한 값 반환
	return heights.back() + 1;
}
//트리의 가장 긴 간선의 길이 구하기
int solve(TreeNode* root) {
	//초기값
	longest = 0;
	//root를 최상위 노드로 하는 잎-잎 경로
	int h = height(root);
	return max(longest, h);
}
//제곱
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]);
}
//자식인지 여부 확인
bool isChild(int parent, int child) {
	//부모의 자식이 아닌 경우
	if (!encloses(parent, child))
		return false;
	for (int i = 0; i < n; i++) {
		//부모도 자식도 아니고 자식의 자식이나 child가 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++) {
		//ch가 root노드의 자식일 경우
		if (isChild(root, ch)) {
			//ch의 노드(ret)의 자식들을 재귀호출을 통해 구한다 
			ret->children.push_back(getTree(ch));
		}
	}
	//자식이 없을 경우(잎 노드)
	return ret;
}
int main() {
	int C;
	cin >> C;
	while (C--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> x[i] >> y[i] >> radius[i];
		}
		TreeNode* root = getTree(0);
		cout << solve(root) << endl;
	}
}

Difference & Faults

자식의 포함여부

내가 처음 코드를 작성할 때 자식과 부모의 포함관계를 판별하기 위해서 중심위치로부터 x의 최대,최소값과 y의 최대,최소값을 비교하여 그 포함여부를 확인하려고 하였다. 근데 해제 코드를 보니 중학교 때 배운 두 원의 위치관계를 사용하더라. r-r'이 두 원점의 길이보다 클 때 한 원이 다른 원에 포함되어있는게 자식과 부모의 위치관계이다.

트리의 높이 구하기

가장 긴 경로를 구할 때 나올 수 있는 경우는 두 가지가 있다. 첫째는 루트에서 잎까지의 거리, 즉 트리의 높이이다. 둘째는 잎과 잎까지의 거리이다. 각 서브트리의 높이와 잎에서 잎까지의 거리를 동시에 구하는 함수 height를 보고 이해하는데 꽤 시간이 오래 걸렸다. 각 노드별로 도출되는 결과를 예상해보며 함수를 따라갔지만 도저히 생각해보아도 노드에서 노드까지의 거리는 저장하나 그 거리를 통해 트리의 높이를 구할 수 있다는게 이해가 안갔다. 다시보니 height함수는 longest라는 전역변수를 함수 내에서 업데이트를 해주고 실제로 반환하는 값은 잎에서 임의 노드까지의 거리이더라. 그래서 최종적으로 함수가 반환하는 값은 트리의 높이였던 것이다.

Impressions

트리의 이용

문제의 가장 큰 특징은 한 원이 다른 원에 포함되어있다는 것이다. 이는 트리의 가장 큰 특징인 관계성과도 비슷하다. 그래서 이 문제를 보고 트리를 통해 해결해야겠다라는 생각은 누구나 쉽게 했을 것이다. 하지만 내가 이 문제의 코드를 구현을 못한 이유는 원의 관계성보다도 트리라는 것에 더 꽂혀서 인거 같다. 정말 처음부터 끝까지 트리의 완성을 목표로 한거 같다. 그러다보니 입력으로 주어지는 원들의 관계성이나 트리를 생성할 때의 복잡함을 보지 못했다.

Summary

아이디어를 생각하기에는 쉬웠지만 구현 과정이 어려웠던 문제이다. 앞에 impression에서도 말했듯이 어떤 자료구조를 사용해야한다는 것이 느낌으로 와닿았다면 무작정 그 자료구조의 구현을 위해 힘쓸 것이 아니라 문제의 특징을 먼저 파악하고 어느 부분에서 특정 자료구조를 사용해야하는지를 파악하자.