N x M 의 이차원 공간에서 섬은 1로 바다는 0으로 표시되는 정보를 바탕으로 섬간에 가장 짧은 거리의 다리를 두어 모든 섬을 이동할 수 있도록 해야하는 문제이다.
A -> B -> C 로 연결되어 있다면 A -> C 가 성립되고 이때 최소비용을 통해 다리를 연결해야한다.
먼저 BFS 탐색을 통해 해당 섬들의 마킹번호를 부여 하였다.
그런 후 순차적으로 해당 블럭을 확인하며 섬간의 직선상 거리정보를 수집했다.(이때 거리가 1이하는 무시)
수집한 모든 간선정보를 직선거리 정보를 기준으로 오름차순으로 정렬한다. 그런 후 순차적으로 탐색하며, 유니온 파인드 알고리즘을 통해 가장 적은 비용으로 모든 섬을 연결할 수 있다
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define MAX 9
int N, M;
int dp[MAX];
int metrix[100][100];
int sft[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };
struct S {
int x;
int y;
};
bool cmp(vector<int>& a, vector<int>& b) {
return a[2] < b[2];
}
void fill_area(int x, int y, int num) {
queue<S> q;
q.push({ x, y });
while (q.size()) {
auto set = q.front();
q.pop();
metrix[set.x][set.y] = num;
for (int i = 0; i < 4; i++) {
int set_x = set.x + sft[i][0];
int set_y = set.y + sft[i][1];
if (set_x >= 0 && set_y >= 0 && set_x < N && set_y < M && metrix[set_x][set_y] == 1) {
q.push({ set_x,set_y });
}
}
}
}
int find(int n) {
if (dp[n] == 0)
return n;
return dp[n] = find(dp[n]);
}
int main() {
vector<vector<int>> buf;
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int k = 0; k < M; k++) {
cin >> metrix[i][k];
}
}
int count = 2;
for (int i = 0; i < N; i++) {
for (int k = 0; k < M; k++) {
if (metrix[i][k] == 1) fill_area(i, k, count++);
}
}
for (int i = 0; i < N; i++) {
int first = 0;
int count = 0;
for (int k = 0; k < M; k++) {
if (metrix[i][k] > 1 && first == 0) first = metrix[i][k]; // 섬위치일 경우 첫 섬미등록시
else if (metrix[i][k] == first) count = 0; // 첫번째 섬을 밟고 있는경우 count 초기화
else if (metrix[i][k] > 1) { // 첫번째 섬이 아닌 다른섬을 밟았을 경우
if (count > 1) {
buf.push_back({ first,metrix[i][k],count });// 그 거리가 2이상일 경우 노드를 추가
}
count = 0;
first = metrix[i][k];
}
else if (first != 0) count++;
}
}
for (int i = 0; i < M; i++) {
int first = 0;
int count = 0;
for (int k = 0; k < N; k++) {
if (metrix[k][i] > 1 && first == 0) first = metrix[k][i]; // 섬위치일 경우 첫 섬미등록시
else if (metrix[k][i] == first) count = 0; // 첫번째 섬을 밟고 있는경우 count 초기화
else if (metrix[k][i] > 1) { // 첫번째 섬이 아닌 다른섬을 밟았을 경우
if (count > 1) {
buf.push_back({ first,metrix[k][i],count });// 그 거리가 2이상일 경우 노드를 추가
}
count = 0;
first = metrix[k][i];
}
else if (first != 0) count++;
}
}
sort(buf.begin(), buf.end(), cmp);
int result = 0;
for (auto& b : buf) {
int A = find(b[0]);
int B = find(b[1]);
if (A != B) { //연결되어 있지 않은 경우
dp[A] = B;
result += b[2];
}
}
int check = 0;
for (int i = 2; i < count; i++) {
if (dp[i] == 0) check++;
}
if (check == 1)
cout << result;
else
cout << -1;
}