코드 복사/붙여넣기 하는 당신이 아름답습니다.

Grid MST

풀이

문제가 좋아서 가져왔다.

1000*1000 크기의 격자에 N(100,000)개의 점이 있다. 모든 점쌍 사이에 가중치가 w(두 점 사이의 맨하탄 거리)인 간선이 있다. 이 때, 이 그래프에서 만들 수 있는 MST의 최소 가중치 합은?

정점 10만개짜리 완전그래프이기에, 나이브한 방법으로 문제를 풀기에는 꽤나 어려워 보인다.

MST를 구성하는 상황을 생각해 보자.

a-bb-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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-11-30 11:24

Read more posts by this author