[백준] 17472 다리 만들기 2

 

A형에 MST가 나왔다던데 이 문제다

완탐으로 풀 수 있는데 괜히 MST한번 써봤따

그리고 틀렸따~~!

 

-1을 출력하는 경우를 잘 생각해야한다

mst에서 정점이 n개일때 간선은 n-1개다

이 성질을 생각해서 -1을 정해주면 예외가 사라진다!

 

MST 자체를 만드는건 유니온 파인드를 이용해 할 수 있다

거리 순으로 정렬하고 만약 A,B 정점이 부모가 다르다면 merge를 시켜준다

그렇게 모든 정점을 연결하면 MST가 완성된다!

 

그럼 문제를 푸는 순서를 생각해보자

1. 먼저 각 섬마다 넘버링을 해서 섬을 구별시킨다 =>dfs

2. 그리고 각 섬에서 다른 섬으로 거리를 구해보자

   이 때 직선으로만 가능하니까 그냥 완탐 돌리자

3. 모든 섬에 대해 그래프를 만들어준다

4. MST를 만들자!

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct Edge {
    int start, end, cost;
    bool operator < (const Edge& other) {
        return cost < other.cost;
    }
};
int p[11];
int map[11][11];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
bool check[11][11];
int n, m;
vector<Edge> Graph;
 
int find(int x) {
    if (p[x] == x) return x;
    return p[x] = find(p[x]);
}
 
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y);
    p[x] = y;
}
 
bool inner(int x, int y) {
    return (0 <= x && x < n && 0 <= y && y < m);
}
 
void dfs(int x, int y, int num) {
    map[x][y] = num;
    check[x][y] = true;
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (inner(nx, ny) && !check[nx][ny] && map[nx][ny]) dfs(nx, ny, num);
    }
}
 
 
int main() {
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %d", &map[i][j]);
        }
    }
 
    int c = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!check[i][j] && map[i][j]) dfs(i, j, c++);
        }
    }
    for (int i = 1; i <= c; i++) p[i] = i;
    Graph.resize(c+1);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!map[i][j]) continue;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                int dist = 0;
                while (inner(nx, ny) && !map[nx][ny]) nx += dx[k], ny += dy[k],dist++;
                if (inner(nx, ny) && (map[nx][ny] != map[i][j]) && map[nx][ny])
                    Graph.push_back({ map[i][j],map[nx][ny],dist });
            }
        }
    }
    
 
    int ans = 0;
    int k = 0;
    sort(Graph.begin(), Graph.end());
    for (int i = 0; i < Graph.size(); i++) {
        Edge e = Graph[i];
        if (e.cost < 2) continue;
        if (find(e.start) != find(e.end)) {
            merge(e.start, e.end);
            ans += e.cost; k += 1;
        }
    }
    printf("%d\n", (k+2 != c) ? -1:ans);
}