Treejin's Note

문제 설명

• 원형의 요새의 정보(x, y, r)이 주어진다.
• 요새는 서로 겹치거나 닿지 않는다.
• 첫번째 주어지는 성벽은 외벽이며, 다른 모든 성벽을 포함한다.

=> 요새 내의 두 지점 간을 이동하기 위해 넘어야하는 성벽의 수의 최대값 출력하기

문제 풀이

요새의 상관관계(?) 분석하기

요새들은 서로 겹치거나 닿지 않는다.

즉 요새들은 다른 요새를 포함하거나, 포함되어있는 상태이다.

이를 트리구조로 표현하면

• 부모 노드 - 넓은 요새
• 자식 노드 - 포함되는 요새

로 표현할 수 있다.

두 요새 간 포함관계를 알기 위해서는 다음 두 조건을 만족해야 한다.

큰 요새를 c1, 작은 요새를 c2라고 한다면,

• c1의 반지름 > c2의 반지름
• c1, c2의 중심간 거리 < c1의 반지름

을 성립하면 c2이 c1에 포함되어있다고 할 수 있다.

이 때, c2의 반지름을 고려하지 않는 이유는 문제에서 요새끼리는 겹치지 않는다는 조건이 있었으므로

두 중심간의 거리가 c1의 반지름보다 작으면 무조건 포함하는 상태임을 확인할 수 있다.

위의 조건을 만족하는지 확인하며 요새간의 관계를 트리구조로 정의하자.

최대 성벽의 수 구하기

두 지점에서 넘어야 하는 최대 성벽의 수는 트리구조로 표현된 요새간의 관계에서

한 노드에서 다른 노드로 향하는 간선의 수가 가장 많은 경우를 출력하면 된다.

간선의 수가 가장 많으려면,

• 루트 노드에서 리프 노드
• 리프 노드에서 또 다른 리프 노드

의 두 가지 경우가 가장 간선이 많을 수 있는 경우이다.

이 경우들을 BFS를 이용해 전부 탐색하고, 최대 간선의 개수를 출력하자.

문제 풀이 코드

#include <iostream>
#include <algorithm>
#include <queue>

#define MAX(a,b)(a > b ? a : b)

using namespace std;

struct Node {
	int x, y, r, parentIdx, childrenCnt = 0;
	int children[100];
};

Node nodes[100];
double dists[100][100];
bool isEnd[100];
int dist = 0;


double getDist(int i, int j) {	// 중심간 거리 구하기
	return sqrt(pow(nodes[i].x - nodes[j].x, 2) + pow(nodes[i].y - nodes[j].y, 2));
}

int findParent(int idx) {	// 부모 노드 찾기
	int parent = 0;
	bool findParent = true;
	while (findParent) {
		findParent = false;
		for (int i = 0; i < nodes[parent].childrenCnt; ++i) {
			int parentIdx = nodes[parent].children[i];
			if (nodes[parentIdx].r > nodes[idx].r && nodes[parentIdx].r > dists[parentIdx][idx]) {
				parent = parentIdx;
				findParent = true;
				break;
			}
		}
	}
	return parent;
}

bool compare_Node(const Node& node1, const Node& node2) {	// 비교 함수
	return node1.r > node2.r;
}

void doBFS(int idx) {	// idx부터 다른 끝점간의 간선수 구하기
	bool visited[100];
	fill_n(visited, 100, false);
	queue<int> q;
	q.push(idx);
	int length = 0;
	while (!q.empty()) {
		int size = q.size();
		while (--size >= 0) {
			int i = q.front();
			q.pop();
			if (visited[i])
				continue;
			visited[i] = true;
			if (isEnd[i]) {
				dist = MAX(dist, length);
			}
			if (nodes[i].parentIdx != -1)
				q.push(nodes[i].parentIdx);
			for (int j = 0; j < nodes[i].childrenCnt; ++j) {
				q.push(nodes[i].children[j]);
			}
		}
		++length;
	}
}

void init() {	// 초기화
	dist = 0;
	fill_n(isEnd, 100, true);
	for (int i = 0; i < 100; ++i) {
		nodes[i].x = 0;
		nodes[i].y = 0;
		nodes[i].r = 0;
		nodes[i].parentIdx = 0;
		nodes[i].childrenCnt = 0;
	}
}

int main() {
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		init();
		int N;
		cin >> N;
		cin >> nodes[0].x >> nodes[0].y >> nodes[0].r;
		nodes[0].parentIdx = -1;
		for (int i = 1; i < N; ++i) {
			cin >> nodes[i].x >> nodes[i].y >> nodes[i].r;
		}

		// 반지름 내림차순으로 정렬하기
		sort(nodes, nodes + 100, &compare_Node);
		
		// 중심간 거리 구하기
		for (int i = 1; i < N; ++i) {
			for (int j = 0; j < i; ++j) {
				dists[i][j] = dists[j][i] = getDist(i, j);
			}
		}

		// 부모, 자식 노드 찾기
		for (int i = 1; i < N; ++i) {
			int parent = findParent(i);
			isEnd[parent] = false;	// 자식이 존재한다 == 리프 노드가 아니다.
			nodes[parent].children[nodes[parent].childrenCnt++] = i;
			nodes[i].parentIdx = parent;
		}
		isEnd[0] = true;

		// 끝점간의 간선수 구하기
		for (int i = 0; i < N; ++i) {
			if (isEnd[i])
				doBFS(i);
		}
		cout << dist << endl;
	}
	return 0;
}