문제
https://www.acmicpc.net/problem/17472
문제해설
각 섬들이 있고
섬들을 다리로 이어 MST그래프를 만들면 된다.
다리를 만드는 기준은
길이가 2이상이고 직선이어야 한다.
문제풀이
bfs함수를 통해 각 섬마다 번호를 붙이고
bfs를 응용한 함수인 makeBridge라는 함수로 다리를 만들어주었다.
makeBridge 함수는 bfs에서 한 방향으로만 계속 가게 바꿔준 것이다.
다리를 만드는 것은 섬에 포함되는 모든 점에 대해서 돌려주었고
길이가 2 이상이면서 최소가 되는 것을 최종 다리로 판별했다.
MST를 만드는 것이 불가능하면 -1을 출력
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define MAX 10
using namespace std;
typedef pair<int, int>P;
int parent[MAX];
int map[11][11];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
queue<P>q, qq;
vector<vector<P>>island(7);
int newMap[11][11];
int n, m;
struct edge {
int st, end, distance;
};
struct cmp {
bool operator()(edge x, edge y) {
return x.distance > y.distance;
}
};
priority_queue<edge, vector<edge>, cmp>arr;
int find(int x) {
if (parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return;
parent[y] = x;
}
bool isUnion(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return true;
return false;
}
void bfs(int cnt) {
while (!qq.empty()) {
int x = qq.front().first;
int y = qq.front().second;
qq.pop();
island[cnt].push_back(P(x, y));
newMap[x][y] = cnt;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (newMap[nx][ny] || map[nx][ny] == 0) continue;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
qq.push(P(nx, ny));
}
}
}
void makeBridge(P now, int num) {
int x = now.first;
int y = now.second;
for (int i = 0; i < 4; i++) {
int nx = x;
int ny = y;
int dis = 0;
while (true) {
nx = nx + dx[i];
ny = ny + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m)
break;
if (newMap[nx][ny] == num) break;
if (newMap[nx][ny] != newMap[x][y] && newMap[nx][ny] != 0) {
if (dis > 1)
arr.push({ num,newMap[nx][ny],dis });
break;
}
dis++;
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < MAX; i++)
parent[i] = i;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
if (map[i][j] == 1)
q.push(P(i, j));
}
}
int cnt = 1;
while (!q.empty()) {
if (newMap[q.front().first][q.front().second]) {
q.pop();
continue;
}
qq.push(P(q.front().first, q.front().second));
bfs(cnt);
cnt++;
q.pop();
}
for (int i = 1; i < island.size(); i++) {
for (int j = 0; j < island[i].size(); j++) {
makeBridge(island[i][j], i);
}
}
int sum = 0;
while (!arr.empty()) {
if (!isUnion(arr.top().st, arr.top().end)) {
sum += arr.top().distance;
merge(arr.top().st, arr.top().end);
}
arr.pop();
}
for (int i = 2; i < cnt; i++) {
if (!isUnion(1, i)) {
cout << -1;
return 0;
}
}
cout << sum;
return 0;
}