https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
이 문제는 최소 신장 트리(MST)를 사용하여서 풀 수 있다. 완전 탐색으로도 그냥 풀 수 있다는데 다음에 풀어봐야겠다.
나는 크루스칼 알고리즘을 사용해서 풀었다.
1. 먼저 BFS로 각 섬에 번호를 붙인다.
2. 각 섬들 간 만들 수 있는 최단 거리의 직선 다리를 다시 BFS로 만들어 본다.
섬이 4개라고 했을 때, 1에서 2, 1에서 3, 1에서 4, 2에서 3, 2에서 4, 3에서 4로 가는 다리를 만들어주면 된다.
(다리 길이가 2 이상이 아니라면 만들 수 없다)
(직선 다리를 만들기 위해서 각 방향마다 쭉쭉 그 방향으로 이동한다.)
3. 다리를 만들 수 있다면 다리 길이와 함께 연결된 두 섬 번호를 벡터에 넣어준다.
4. 모든 다리를 구했으면 크루스칼 알고리즘을 이용하여 최소 스패닝 트리를 만들어준다.
크루스칼 알고리즘을 간단히 설명하면
간선들을 가중치를 기준으로 오름 차순 정렬한 후에
가중치가 제일 작은 것부터 연결되지 않은 간선들을 순차적으로 선택해나가는 알고리즘이다.
그리고 정점이 n 개라면 간선의 개수는 n-1개이므로 선택한 간선이 n-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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
|
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int map[10][10];
int island[10][10];
int p[7];
vector<pair<int, pair<int, int>>> vt;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int getParent(int a) {
if (p[a] == a) return a;
return p[a] = getParent(p[a]);
}
void unionSet(int a, int b) {
int rootA = getParent(a);
int rootB = getParent(b);
p[rootA] = rootB;
}
//u번 섬에서 v번 섬으로 가는 직선 최단 거리를 구한다.
void getMinDist(int u, int v) {
queue < pair<int, int>> q;
//u번 섬에 있는 칸들을 모두 큐에 넣는다.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (island[i][j] == u) {
q.push(make_pair(i, j));
}
}
}
int mindist = 10;
int x, y;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
int dist = 0;
//한방향으로 계속 이동
while (true) {
//범위를 넘어간 경우
if (nx < 0 || ny < 0 || nx >= n || ny >= m) break;
//같은 섬인경우 더 탐색하지 않는다.
if (island[nx][ny] == u) break;
if (island[nx][ny] == v) {
//v번섬인 경우 최소거리와 비교후 더 탐색하지 않는다.
if (dist > 1 && mindist > dist) mindist = dist;
break;
}
else if (island[nx][ny] == 0) {
//바다인 경우 거리증가하고 이동
dist++;
nx += dx[k];
ny += dy[k];
}
else {
//다른 섬인 경우 더 탐색하지 않는다.
break;
}
}
}
}
//최소거리가 초기값이 아니라면 벡터에 최소거리와 섬의 번호를 넣는다.
if (mindist != 10) vt.push_back(make_pair(mindist, make_pair(u, v)));
}
void bfs(int x, int y, int num) {
queue<pair<int, int> > q;
q.push(make_pair(x, y));
island[x][y] = num;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (map[nx][ny] == 0) continue;
if (island[nx][ny] != 0) continue;
q.push(make_pair(nx, ny));
island[nx][ny] = num;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
}
}
//섬에 번호를 붙인다.
int num = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//바다인 경우
if (map[i][j] == 0) continue;
//이미 번호를 붙인 경우
if (island[i][j] != 0) continue;
bfs(i, j, ++num);
}
}
//위에서 번호를 붙인 num이 섬의 개수
//각 섬들간의 만들수 있는 다리를 모두 만든다.
for (int i = 1; i <= num - 1; i++) {
for (int j = i + 1; j <= num; j++) {
getMinDist(i, j);
}
}
int size = vt.size();
//거리를 기준으로 오름차순 정렬
sort(vt.begin(), vt.end());
//부모 배열 초기화(처음 부모는 자기 자신)
for (int i = 1; i <= num; i++) p[i] = i;
int sum = 0;
int cnt = 0;
int index = 0;
int u, v, dist;
//선택한 간선의 개수가 섬의개수 -1이 될때까지 간선을 선택한다.
while (cnt < num - 1) {
if (index == size) {
//모든 섬을 연결하는 것이 불가능하다
cout << -1 << "\n";
return 0;
}
dist = vt[index].first;
u = vt[index].second.first;
v = vt[index].second.second;
index++;
if (getParent(u) == getParent(v)) {
//이미 연결되어 있다.
continue;
}
else {
//연결되어 있지 않다면 합친다.
unionSet(u, v);
//연결된 간선의 수 증가
cnt++;
//다리 길이에 합쳐준다.
sum += dist;
}
}
cout << sum << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 5567. 결혼식 (0) | 2019.11.13 |
|---|---|
| [BOJ] 7662. 이중 우선순위 큐 (0) | 2019.11.13 |
| [BOJ] 2146. 다리 만들기 (0) | 2019.10.16 |
| [BOJ] 17471. 게리맨더링 (0) | 2019.10.16 |
| [BOJ] 17141. 연구소 2 (0) | 2019.09.06 |