백준 BOJ 10058번 : 센서 네트워크 풀이 (Ruby V, 이분 매칭)
백준에서 3600문제 넘게 풀면서 루비 난이도 문제를 처음으로 푼 기념으로 이 문제만 별개의 포스트로 정리해본다.
무려 월드 파이널 문제이며 그 해 문제 중에서도 solved.ac 기준으로 난이도가 가장 높은 문제이다.
백준 BOJ 10058번 : 센서 네트워크
문제 난이도 : Ruby V
알고리즘 분류 : 기하학, 이분 매칭
2차원 좌표 평면 상에 N개의 점이 주어질 때, 어떤 두 점의 거리도 M 이하가 되게 하는 점들의 집합의 최대 크기와 그 때의 점들의 번호 목록을 구하는 문제이다.
가장 naive하게 생각할 수 있는 풀이는 각 점을 집합에 포함시키거나 시키지 않은 뒤 해당 집합에서 가장 먼 두 점 사이의 거리가 M 이하라면 집합의 최대 크기를 비교하여 갱신해주는 방식이 있다.
이 때의 시간 복잡도는 최소 O(2^N) 이상이 되고, 당연히 시간 초과이다.
N ≤ 100으로 N의 제한이 매우 크지 않음에 주목하자.
임의의 두 점이 집합에서 가장 먼 두 점이라고 먼저 가정한 뒤, 이 집합에 포함될 수 있는 점들을 탐색한다면, 이중 for문 내에서 별개의 이중 for문을 더 돌려서 O(N^4)가 되어도 충분히 돌아간다.
따라서 두 점을 잡고 이 두 점 사이의 거리가 집합에서 가장 먼 두 점이 되도록 집합을 완성하여 답을 구해보자.
결정한 두 점이 A, B이고, 두 점 사이의 거리가 r ≤ M이라고 할 때, 점 A에서 반지름 r인 원과 점 B에서 반지름 r인 원을 그려서 그 교집합에 포함되는 점들이 집합에 포함될 수 있는 점들의 후보가 된다.
하지만 두 원의 교점 사이의 거리가 r보다 크므로 반례가 존재하게 된다. (예를 들면 위의 그림에서 선분 xy가 반례가 된다.)
여기서 핵심 아이디어가 필요하다.
교집합에 포함되는 점들을 선분 AB를 기준으로 위에 위치하는 점들과 아래에 위치하는 점들로 나눠보자.
실제로는 두 점 A, B가 x축에 평행하게 위치하지 않으므로, ccw를 사용하여 ccw 값을 0을 기준으로 두 부분으로 나누어 선분 AB를 기준으로 양쪽에 위치하는 점들로 나누면 된다.
그러면 같은 그룹에 속한 점들 사이의 거리는 반드시 r 이하이다.
따라서 점들을 위 그룹과 아래 그룹으로 나누어 거리가 r보다 큰 위의 점과 아래의 점 사이를 간선으로 연결하여 이분 그래프를 만들어주고, 여기서 이분 매칭을 수행하여 최대 매칭 수만큼 점들에서 빼주면 그것이 최종적인 집합의 크기가 된다. 즉, 이제 이 집합에는 어떤 두 점 사이의 거리도 r 이하가 된다.
문제는 집합의 크기는 위 그룹 + 아래 그룹 - 최대 매칭 수임을 알 수 있는데 일부 점을 뺄 때 어떤 점을 빼야하냐는 것이다. (최종적으로 점들의 번호를 구해야하므로)
여기서 최소 정점 커버에 대한 다음의 정리를 사용해야한다.
이분 그래프에서 왼쪽 정점 그룹을 L, 오른쪽 정점 그룹을 R이라고 하자.
이분 매칭이 수행된 이분 그래프에서 alternating path란 최대 매칭에 포함되는 간선과 포함되지 않는 간선을 번갈아가며 선택하면서 이동하는 경로를 말한다.
L의 최대 매칭에 포함되지 않는 점들에서 시작하여 alternating path로 도달할 수 있는 모든 정점들의 집합을 X라고 하자.
그러면 최소 정점 커버 = (L - X) ∪ (R ∩ X)이다.
이제 풀이가 끝났다. 풀이를 요약하면 다음과 같다.
1. 가능한 모든 두 점의 조합들 중 거리가 M 이하인 두 점에 대해 다음을 반복한다.
2. 두 점을 기준으로 반지름이 두 점 사이의 거리인 원을 그려 교집합에 들어오는 점들을, 두 점을 잇는 선분을 기준으로 ccw값의 부호에 따라 두 그룹으로 나눈다.
3. 거리가 r 이상인 점들 사이에 간선을 연결해주고 이분 매칭을 수행하여 최소로 지워야 하는 점의 수를 구하고, 집합의 크기를 구한다.
4. 집합의 원소를 구하기 위해 최소 정점 커버에 대한 정리를 사용하여 구해준다.
5. 이렇게 구한 집합들 중에서 크기가 가장 큰 것을 답으로 출력해주면 된다.
이것을 코드로 구현하면 다음과 같다.
아래는 정답 처리를 받은 풀이 코드이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { double x, y; int n; };
double dis(s a, s b) {
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double ccw(s a, s b, s c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
vector<vector<int>> adj;
vector<int> ll, rr;
vector<bool> vis;
bool f(int x) {
vis[x] = true;
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(rr[y] == -1 || (!vis[rr[y]] && f(rr[y]))) {
ll[x] = y, rr[y] = x;
return true;
}
}
return false;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
double M; cin >> M;
vector<s> v(N);
for(int i=0; i<N; i++) {
cin >> v[i].x >> v[i].y;
v[i].n = i+1;
}
vector<int> ans;
ans.push_back(1);
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++) {
double r = dis(v[i], v[j]);
if(r > M) continue;
vector<s> u, w;
for(int k=0; k<N; k++) {
if(dis(v[i], v[k]) > r || dis(v[j], v[k]) > r) continue;
if(ccw(v[i], v[j], v[k]) >= 0) u.push_back(v[k]);
else w.push_back(v[k]);
}
adj.clear();
adj.resize(u.size());
for(int k=0; k<u.size(); k++)
for(int l=0; l<w.size(); l++)
if(dis(u[k], w[l]) > r) adj[k].push_back(l);
ll.clear(); ll.resize(u.size(), -1);
rr.clear(); rr.resize(w.size(), -1);
int match = 0;
for(int k=0; k<u.size(); k++) {
vis.clear();
vis.resize(u.size());
if(f(k)) match++;
}
if(u.size() + w.size() - match <= ans.size()) continue;
vector<bool> lvis(u.size()), rvis(w.size());
for(int k=0; k<u.size(); k++) {
if(ll[k] != -1 || lvis[k]) continue;
lvis[k] = true;
queue<pair<bool, int>> q;
q.push({true, k});
while(!q.empty()) {
bool isLeft = q.front().first;
int x = q.front().second;
q.pop();
if(isLeft) {
for(int l=0; l<adj[x].size(); l++) {
int y = adj[x][l];
if(ll[x] != y && !rvis[y]) {
rvis[y] = true;
q.push({false, y});
}
}
}
else {
for(int l=0; l<u.size(); l++) {
int y = l;
if(lvis[y]) continue;
if(count(adj[y].begin(), adj[y].end(), x) == 0) continue;
for(int m=0; m<adj[y].size(); m++) {
if(adj[y][m] != x) continue;
if(rr[x] == y) {
lvis[y] = true;
q.push({true, y});
}
}
}
}
}
}
ans.clear();
for(int k=0; k<u.size(); k++)
if(lvis[k]) ans.push_back(u[k].n);
for(int k=0; k<w.size(); k++)
if(!rvis[k]) ans.push_back(w[k].n);
}
cout << ans.size() << "\n";
for(int i=0; i<ans.size(); i++) cout << ans[i] << " ";
cout << "\n";
}