알고스팟 요새 FORTRESS

두 원은 만나지 않으면서 겹치치 않는다는 조건이 있다

결국 1. 두 원은 서로 떨어져 있거나 2. 하나의 원이 다른 하나의 원 안에 있거나 둘 중에 하나다

 

원들이 모두 계층적 구조를 가지고 있기 때문에, 트리로 구성할 수 있다. 이전에 서로 원들을 모두 비교하면서 자신의 부모를 찾는다. 조건을 만족하면서 반지름이 작은 부모인 바로 부모노드만을 저장한다. 그 정보를 가지고 트리를 구성하게 된다

 

그리고 최장 거리는 리프노드와 리프노드 혹은 리프노드와 루트와의 거리이므로 bfs를 돌려서 그 거리를 구할 수 있게 된다

 

문제: https://algospot.com/judge/problem/read/FORTRESS

깃허브주소: https://github.com/surinoel/boj/blob/master/FORTRESS.cpp

 

	#include <queue>
	#include <vector>
	#include <cstring>
	#include <iostream>
	using namespace std;
	struct circle {
	int x, y, r;
	circle() {}
	circle(int x, int y, int r) : x(x), y(y), r(r) {
	}
	};
	vector<circle> a; // 원 정보
	vector<int> tree[101]; // 트리 정보
	vector<pair<int, int>> p; // 부모의 노드와 반지름
	int dist[101]; // bfs를 위한 배열
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int tc;
	cin >> tc;
	while (tc--) {
	memset(dist, -1, sizeof(dist));
	int n;
	cin >> n;
	a = vector<circle>(n + 1);
	p = vector<pair<int, int>>(n + 1);
	for (int i = 1; i <= n; i++) {
	int x, y, r;
	cin >> x >> y >> r;
	a[i] = circle(x, y, r);
	tree[i] = vector<int>();
	}
	for (int i = 1; i < n; i++) {
	for (int j = i + 1; j <= n; j++) {
	int x1, y1, r1, x2, y2, r2;
	x1 = a[i].x, y1 = a[i].y, r1 = a[i].r;
	x2 = a[j].x, y2 = a[j].y, r2 = a[j].r;
	int d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
	if (d > ((r1 + r2) * (r1 + r2))) continue; // 서로 속하지 않는다면
	if (!(d < ((r1 - r2) * (r1 - r2)))) continue;
	if (r1 > r2) {
	if (p[j].second != 0) { // 부모 정보가 있지만 저장된 반지름이 현재보다 크다면
	if (p[j].second > r1) {
	p[j] = make_pair(i, r1);
	}
	}
	else {
	p[j] = make_pair(i, r1);
	}
	}
	else {
	if (p[i].second != 0) {
	if (p[i].second > r2) {
	p[i] = make_pair(j, r2);
	}
	}
	else {
	p[i] = make_pair(j, r2);
	}
	}
	}
	}
	for (int i = 1; i <= n; i++) { // 업데이트 된 부모 정보를 위해 트리정보 구성
	if (p[i].first == 0) { // 부모 정보가 없다면 최외곽 정보
	tree[0].push_back(i);
	tree[i].push_back(0);
	}
	else {
	tree[p[i].first].push_back(i);
	tree[i].push_back(p[i].first);
	}
	}
	queue<int> q;
	q.push(0);
	dist[0] = 0;
	int node = 0, mdist = 0;
	while (!q.empty()) {
	int x = q.front();
	q.pop();
	for (int k = 0; k < tree[x].size(); k++) {
	int y = tree[x][k];
	if (dist[y] != -1) continue;
	dist[y] = dist[x] + 1;
	if ((mdist == 0 || dist[y] > mdist) && y != 0) { // 0번 노드가 아니면서 최장 거리
	mdist = dist[y];
	node = y;
	}
	q.push(y);
	}
	}
	memset(dist, -1, sizeof(dist));
	dist[node] = 0;
	q = queue<int>();
	q.push(node);
	mdist = 0;
	while (!q.empty()) {
	int x = q.front();
	q.pop();
	for (int k = 0; k < tree[x].size(); k++) {
	int y = tree[x][k];
	if (dist[y] != -1) continue;
	dist[y] = dist[x] + 1;
	if ((mdist == 0 || dist[y] > mdist) && y != 0) { // 0번 노드가 아니면서 최장 거리라면
	mdist = dist[y];
	}
	q.push(y);
	}
	}
	cout << mdist << '\n';
	}
	return 0;
	}

view raw FORTRESS.cpp hosted with ❤ by GitHub