[BOJ] 17472 - 다리 만들기2

문제 링크

처음 문제를 봤을 때 딱 들었던 생각은,

1. BFS문제구나
2. 이 문제를 굳이 최소신장트리 알고리즘을 써서까지 풀어야 하는가?

이 두가지였다. 그러나 코드를 완성해가면서 이 문제는 MST문제가 맞았구나.. 하는 확신이 들었다.

이 문제를 풀며 실수했던 점을 기록한다.

1. 다리의 최소 길이는 2 이상이라는 점을 간과했다.
2. 다리가 겹치는 것은 따로 길이를 계산한다는 점을 간과했다.(그러나 이 조건 덕분에 더욱 쉽게 풀 수 있었다. 친절하다.)
3. 마지막 확인 과정에서 parent배열을 바로 불러와서 문제가 있었다.

교훈) union-find를 사용할 때 부모의 확인은 반드시 find를 통해 불러오도록 하자!

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
#define INF 99999999
using namespace std;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int n, m, mp[15][15], island[15][15], cnt, parent[10], dist[10][10];
int dr[4] = { 1,-1, 0, 0 }, dc[4] = { 0,0,1,-1 };
queue<P> q;
priority_queue<T> pq;

bool isInRange(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void bfs(int x, int y) { // 섬 번호 매기기
    q.push({ x,y });
    island[x][y] = cnt;
    while (!q.empty()) {
        int xx = q.front().first, yy = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            x = xx + dr[i];
            y = yy + dc[i];
            if (isInRange(x, y) && mp[x][y] && !island[x][y]) {
                q.push({ x, y });
                island[x][y] = cnt;
            }
        }
    }
}

int find(int now) {
    if (parent[now] == now) return now;
    return parent[now] = find(parent[now]);
}

void merge(int x, int y) {
    parent[find(y)] = find(x);
    find(y);
}

int main(void) {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", mp[i] + j);
        }
    }

    // 섬 번호 매기기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mp[i][j] && !island[i][j]) {
                cnt++;
                bfs(i, j);
            }
        }
    }

    for (int i = 1; i <= cnt; i++) {
        parent[i] = i;
    }

    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j <= cnt; j++) {
            if (i == j) continue;
            dist[i][j] = INF;
        }
    }

    // 간선 가중치 업데이트
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!mp[i][j]) continue;
            for (int k = 0; k < 4; k++) {
                int x = i + dr[k], y = j + dc[k];
                if (isInRange(x, y) && !mp[x][y]) {
                    int d = 0;
                    while (isInRange(x, y) && !mp[x][y]) {
                        x += dr[k];
                        y += dc[k];
                        d++;
                    }
                    if (isInRange(x, y) && d > 1)
                        dist[island[i][j]][island[x][y]] = dist[island[x][y]][island[i][j]] = min(d, dist[island[i][j]][island[x][y]]);
                }
            }
        }
    }

    for (int i = 1; i <= cnt; i++) {
        for (int j = i + 1; j <= cnt; j++) {
            if (dist[i][j] != INF)
                pq.push({ -dist[i][j], i, j });
        }
    }

    int ans = 0;

    while (!pq.empty()) {
        int x = get<1>(pq.top()), y = get<2>(pq.top()), c = get<0>(pq.top());
        pq.pop();
        if (find(x) != find(y)) {
            merge(x, y);
            ans -= c;
        }
    }
    for (int i = 2; i <= cnt; i++) {
        if (find(i) != find(1)) {
            ans = -1;
            break;
        }
    }
    printf("%d", ans);
    return 0;
}