풀이
문제가 좋아서 가져왔다.
1000*1000 크기의 격자에 N(100,000)개의 점이 있다. 모든 점쌍 사이에 가중치가 w(두 점 사이의 맨하탄 거리)인 간선이 있다. 이 때, 이 그래프에서 만들 수 있는 MST의 최소 가중치 합은?
정점 10만개짜리 완전그래프이기에, 나이브한 방법으로 문제를 풀기에는 꽤나 어려워 보인다.
MST를 구성하는 상황을 생각해 보자.
a-b와 b-c가 있고, b를 지나는 것이 최단인 a-c가 존재한다면, a-c를 MST에 포함시키는 것 보다 더 나은 방법(a-b, b-c)이 항상 존재한다.
격자의 크기가 최대 1000*1000임에 주목하자.
우리는 모든 점에서 동시에 4방향 flood-fill을 돌릴 것이다.
플러드필 영역이 커지다 보면 어떤 두 정점의 영역이 서로 맞닿는 시점이 있는데, 이 때 맞닿는 두 영역의 반지름 합이 두 정점 사이의 최단 거리이다.
두 정점의 맨하탄 거리를 가중치로 정의했고 BFS flood-fill을 돌리고 있기 때문에, 두 영역이 최초로 만나는 시점이 최단임은 자명해 보인다.
이제 우리는, 모든 정점에 대해, 플러드필 영역이 맞닿는 간선만 고려해서 MST를 구성해도 가중치 합이 최소인 스패닝 트리를 구성할 수 있음을 알 수 있다.
격자 크기와 정점 개수가 더 큰 버전의 같은 문제 https://www.acmicpc.net/problem/15929도 있는데 이 문제는 더 어렵다. (크니까 당연히 어렵겠지?)
저 문제에 대한 풀이는 여기에 있다.
저 문제도 곧 풀어서 포스팅 할 예정!
끝!!
코드
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int n_ = 1e5 + 3;
const int xy_ = 1e3 + 3;
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
int n;
int dst[xy_][xy_], chk[xy_][xy_];
int par[n_];
ll ans;
struct abc { int x, y, idx; };
struct edg { int x, y; ll dst; };
queue<abc> que;
vector<edg> edgs;
void input() {
memset(dst, -1, sizeof(dst));
memset(chk, -1, sizeof(chk));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d %d", &x, &y);
if (dst[x][y] != -1) {
continue;
}
que.push({ x,y,i });
dst[x][y] = 0;
chk[x][y] = i;
}
}
int find(int u) {
if (u == par[u]) return u;
return par[u] = find(par[u]);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u > v) swap(u, v);
if (u == v) return;
par[u] = v;
}
void process() {
while (!que.empty()) {
abc now = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
int nx = now.x+dx[i], ny = now.y+dy[i];
if (nx < 0 || ny < 0 || nx >= 1000 || ny >= 1000) {
continue;
}
if (dst[nx][ny] == -1) {
dst[nx][ny] = dst[now.x][now.y] + 1;
chk[nx][ny] = now.idx;
que.push({ nx,ny,now.idx });
}
else {
int u = chk[now.x][now.y];
int v = chk[nx][ny];
ll k = (ll)dst[now.x][now.y]+dst[nx][ny]+1;
edgs.push_back({ u,v,k });
}
}
}
sort(edgs.begin(), edgs.end(), [&](edg &i, edg &j){return i.dst<j.dst;});
for (int i = 0; i <= n; i++) {
par[i] = i;
}
for (auto now : edgs) {
int u = find(now.x), v = find(now.y);
if (u == v) {
continue;
}
merge(u, v);
ans += now.dst;
}
}
void output() {
printf("%lld\n", ans);
}
int main() {
input();
process();
output();
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이