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

🤔생각

이게 왜 트리문제이지...? 라는 생각이 들었다. 다른 방식으로 풀 수 있을거란 생각이 있었기 때문이다. 하지만 생각했던 방식은 틀린 방법이었고 왜 트리 문제인지 깨달을 수 있었다. 원이 다른 원에 포함되는 것이 계층구조인 트리구조와 유사하기 때문에 트리문제로 분류된 것이다. 그래서 입력을 트리로 구조화 시키고 트리의 지름을 구하면 될것이라고 생각하였다. 이때 트리를 구조화 시키는 것은 반지름이 가장 큰 원부터 가장 작은 원까지 내림차순으로 해야한다. 반드리 그래야만 하는 것은 아니지만 그렇지 않으면 트리를 확장하는 코드가 복잡해질것이다. 지름을 구하는 방법은 처음 태초의 root부터 가장 긴 리프노드를 찾는다. 그 다음에 그 리프노드부터 또 다시 가장 긴 리프노드까지의 길이를 구하면 그것이 지름이 된다. 보통 트리 지름의 길이를 구할 때 DFS나 BFS를 사용한다.

😀코드

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>

using namespace std;

typedef struct Info{
	int x, y, r;
}Info;

typedef struct TreeNode{
	Info data;
	TreeNode* parent;
	int id;
	vector<TreeNode*> children;
}TreeNode;

Info info[1000];
bool visited[1000];
int N, maxLen;
int assignId;
TreeNode* tmp;

double distanceTwoP(Info p1, Info p2) {
	return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

void expandTree(TreeNode* root, Info data) {
	int flag = 1;
	for (int i = 0; i < root->children.size(); i++) {
		if (distanceTwoP(root->children[i]->data, data) < root->children[i]->data.r) {
			expandTree(root->children[i], data);	//내부로 들어가는 과정
			flag = 0;
		}
	}

	if(flag)
		root->children.push_back(new TreeNode{ data, root, assignId++});
}

void ans(TreeNode* root, int len, int flag) {
	visited[root->id] = 1;

	if (((flag == 1 && root->parent == nullptr) || root->children.empty()) && maxLen < len) {
		tmp = root;
		maxLen = len;
	}
	if (flag == 1 && root->parent != nullptr && !visited[root->parent->id])
		ans(root->parent, len + 1, flag);
	for (int i = 0; i < root->children.size(); i++) {
		if (!visited[root->children[i]->id])
			ans(root->children[i], len + 1, flag);
	}
}

void Free(TreeNode *root) {
	for (int i = 0; i < root->children.size(); i++)
		Free(root->children[i]);

	root->children.clear();
}
int main(void) {
	int C;
	TreeNode root;
	Info init = { -1, -1, -1 };

	cin >> C;

	for (int i = 0; i < C; i++) {
		assignId = maxLen = 0;
		memset(visited, 0, sizeof(visited));
		root.parent = nullptr;
		cin >> N;

		for (int j = 0; j < N; j++) 
			cin >> info[j].x >> info[j].y >> info[j].r;
		
		for(int j = 0; j < N; j++)
			for(int z = 0; z < N  - 1 - j; z++)
				if (info[z].r < info[z + 1].r) {
					Info tmp = info[z];
					info[z] = info[z + 1];
					info[z + 1] = tmp;
				}

		root.data = info[0];
		root.id = assignId++;

		for (int j = 1; j < N; j++)
			expandTree(&root, info[j]);

		ans(&root, 0, 0);
		maxLen = 0;
		memset(visited, 0, sizeof(visited));
		ans(tmp, 0, 1);
		cout << maxLen << endl;
		Free(&root);
	}

	return 0;
}

👏후기

이 문제를 접하기 전에 백준에서 트리의 지름을 구하는 문제를 접해본것이 큰 도움이 됐다. 그렇지 않았다면 요새를 트리로 구조화만 시켜놓고 답을 구하지 못 했을 것이다.