BOJ 9373 - 복도 뚫기

문제

링크: https://www.acmicpc.net/problem/9373

복도에 센서들이 있고 센서들을 피해 복도를 통과할 수 있는 가장 큰 원의 반지름을 구하는 문제이다.

복도의 너비가 주어지고, 각 센서들의 좌표 x, y와 반지름 r이 주어진다.

처음에는 센서와 센서 사이에 존재할 수 있는 원들로 어떻게 MST를 잘 만들면 되지 않을까했는데, 가장 큰 원의 반지름을 구하기가 힘들었다. 하루 정도 계속 틀리고 고민하고를 반복하다 솔루션을 찾아봤다.

솔루션을 보자마자 와 이게 뭐지 싶었다. 이렇게 풀 수도 있구나 신기했다.

풀이

최소 신장 트리 문제는 맞았고 원과 원 사이의 끼인 원으로 어떻게 하는 것도 맞았다. 근데 최종형태가 이런 식이었다.

양쪽 벽을 큰 집합이라고 생각하고 두 집합이 연결될 때까지 MST를 만든다. 크루스칼 알고리즘으로 해결하면 간단하다.

센서(원)의 개수가 $n \leq 1,000$ 이라서 모든 원들 사이의 작은 원의 거리를 간선으로 연결해도 무방하다. ($N$이 크면 어떡할까? 평방분할 같은거로 좌표압축해서 빠르게 찾아야 하나...? 고민해봐야겠다)

왼쪽 벽 집합과 오른쪽 벽 집합이 같아졌다는 것은 간선이 서로 연결되었다는 의미이다. 그리고 이것은 다시 말해, 복도를 지날 수 있는 가장 큰 원을 찾았다는 뜻이다. 어떻게 이런 생각을 하는 걸까..

	#include <bits/stdc++.h>
	using namespace std;
	using lld = long long;
	struct edge {
	int u, v;
	double w;
	bool operator < (const edge& e) const {
	return w < e.w;
	}
	};
	int find(vector<int>& r, int k) {
	if (k == r[k]) return k;
	return r[k] = find(r, r[k]);
	}
	bool merge(vector<int>& root, int p, int q) {
	p = find(root, p);
	q = find(root, q);
	if (p == q) return false;
	root[q] = p;
	return true;
	}
	struct circle {
	int x, y, r;
	double dist(const circle& c) {
	lld dx = x - c.x, dy = y - c.y;
	return sqrt(dx*dx + dy*dy) + 1e-8;
	}
	double distBound(const circle& c) {
	return max(0., dist(c) - r - c.r);
	}
	};
	int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
	int w, n;
	scanf("%d %d", &w, &n);
	vector<circle> a(n);
	for (int i = 0; i < n; ++i)
	scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].r);
	vector<edge> E;
	vector<int> group(n + 2);
	int LEFT = n, RIGHT = n + 1; // 왼쪽 벽과 오른쪽 벽
	E.push_back({ LEFT, RIGHT, w + .0 });
	for (int i = 0; i < n; ++i) {
	group[i] = i;
	E.push_back({ i, LEFT, 0. + max(0, a[i].x - a[i].r) }); // left
	E.push_back({ i, RIGHT, 0. + max(0, w - a[i].x - a[i].r) }); // right
	for (int j = i + 1; j < n; ++j) {
	E.push_back({ i, j, a[i].distBound(a[j]) });
	}
	}
	group[LEFT] = LEFT;
	group[RIGHT] = RIGHT;
	sort(E.begin(), E.end());
	double ans = w;
	for (auto& e : E) {
	// 가장 짧은 거리부터 탐색
	if (merge(group, e.u, e.v)) {
	// 왼쪽과 오른쪽 벽이 서로 연결되었다면
	// 즉, 길이 막혔거나 지나갈 수 있는 가장 작은 통로를 발견
	if (find(group, LEFT) == find(group, RIGHT)) {
	printf("%.6f\n", e.w / 2.0);
	break;
	}
	}
	}
	}
	return 0;
	}

view raw boj-9373.cpp hosted with ❤ by GitHub