BOJ 17472 다리 만들기 2

1 개요[ | ]

BOJ 17472 다리 만들기 2
2 C++[ | ]

#include <bits/stdc++.h>
using namespace std;
 
typedef struct edge {
    int s;
    int e;
    int dist;
} edge;

int N, M;
int A[10][10];
int parent[11];
vector<edge> v;
bool visited[10][10];
bool checked[10][10][10];

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int Find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = Find(parent[x]);
}
 
void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if(a > b) {
        parent[a] = b;
    } else {
        parent[b] = a;
    }
}

void check(int x, int y, int k, int sn) {
    int cnt = 0;
    while (true) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        int a = A[nx][ny];
        if (nx < 0 || ny < 0 || nx >= N || ny >= M || a == sn) break;
        if (a == 0) {
            x = nx;
            y = ny;
            cnt++;
            continue;
        }
        if (a != sn) {
            if (cnt < 2) break;
            if (checked[sn][a][cnt] || checked[a][sn][cnt]) break;
            checked[sn][a][cnt] = true;
            checked[a][sn][cnt] = true;
            v.push_back({sn, a, cnt});
            break;
        }
    }
}

void bfs(int sx, int sy, int num) {
    queue<pair<int,int>> q;
    q.push({sx, sy});
    visited[sx][sy] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        A[x][y] = num;
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M || A[nx][ny]==0 || visited[nx][ny]) continue;
            q.push({nx, ny});
            visited[nx][ny] = true;
        }
    }
}

void solve() {
    int cnt = 0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (visited[i][j] || !A[i][j]) continue;
            cnt++;
            bfs(i, j, cnt);
        }
    }
    for (int i=1; i<=cnt; i++) {
        parent[i] = i;
    }
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (A[i][j] == 0) continue;
            for (int k=0; k<4; k++) {
                check(i, j, k, A[i][j]);
            }
        }
    }
    sort(v.begin(), v.end(), [](edge a, edge b) { return a.dist < b.dist; });
    int answer = 0;
    for (int i=0; i<v.size(); i++) {
        int sroot = Find(v[i].s);
        int eroot = Find(v[i].e);
        if (sroot == eroot) continue;
        Union(sroot, eroot);
        answer += v[i].dist;
    }
    int root = Find(1);
    for (int i=2; i<=cnt; i++) {
        if (root != Find(i)) {
            cout << "-1";
            return;
        }
    }
    cout << answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            cin >> A[i][j];
         }
    }
    solve();
}