반응형
https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
문제풀이
1. 섬들을 BFS를 이용해 번호를 붙여준다.
2. 번호를 붙여진 섬들간의 간선의 길이를 구한다
3. 크루스칼 알고리즘을 이용해 최소스패닝트리의 가중치를 구한다.
#include <bits/stdc++.h>
using namespace std;
int unf[7];
int Find(int x) {
if (x == unf[x]) {
return x;
}
else return unf[x] = Find(unf[x]);
}
void Union(int a, int b) {
a = Find(a);
b = Find(b);
if (a != b) {
unf[a] = b;
}
}
struct Edge {
int x, y, val;
bool operator<(const Edge& b)const {
return val > b.val;
}
};
int n, m;
bool arr_[11][11];
int arr[11][11];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int cnt = 1;
priority_queue<Edge> Kruskal;
void make_island() {
queue<pair<int,int> > Q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr_[i][j] && arr[i][j] == 0) {
arr[i][j] = cnt;
Q.push({ i,j });
while (!Q.empty()) {
int x = Q.front().first;
int 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 || nx >= n || ny < 0 || ny >= m || arr_[nx][ny] == 0 || arr[nx][ny] > 0) continue;
arr[nx][ny] = cnt;
Q.push({ nx,ny });
}
}
cnt++;
}
}
}
return;
}
void make_edge() {
for (int i = 0; i < n; i++) {
int start = 0, end = 0, dist = 0;
for (int j = 0; j < m; j++) {
if (arr[i][j] != 0) {
if (start == 0) {
start = arr[i][j];
dist = 0;
}
else {
if (arr[i][j] == start) {
dist = 0;
}
else {
end = arr[i][j];
if (dist >= 2) Kruskal.push({ start,end,dist });
start = end;
end = 0;
dist = 0;
}
}
}
else if (arr[i][j] == 0) {
dist++;
}
}
}
for (int i = 0; i < m; i++) {
int start = 0, end = 0, dist = 0;
for (int j = 0; j < n; j++) {
if (arr[j][i] != 0) {
if (start == 0) {
start = arr[j][i];
dist = 0;
}
else {
if (arr[j][i] == start) {
dist = 0;
}
else {
end = arr[j][i];
if (dist >= 2) Kruskal.push({ start,end,dist });
start = end;
end = 0;
dist = 0;
}
}
}
else if (arr[j][i] == 0) {
dist++;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 7; i++) {
unf[i] = i;
}
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr_[i][j];
}
}
make_island();
make_edge();
int ans = 0;
while (!Kruskal.empty()) {
int x = Kruskal.top().x;
int y = Kruskal.top().y;
int val = Kruskal.top().val;
Kruskal.pop();
if (Find(x) != Find(y)) {
Union(x, y);
ans += val;
}
}
int comp = Find(1);
for (int i = 1; i <= cnt-1; i++) {
if (comp != Find(i)) {
cout << -1 << '\n';
return 0;
}
}
cout << ans << '\n';
return 0;
}
반응형
'Algorithm > problem' 카테고리의 다른 글
| 백준 10423번: 전기가 부족해 - Prim MST 프림 최소스패닝트리 (0) | 2022.02.18 |
|---|---|
| 백준 1774번 : 우주신과의 교감 - 크루스칼 MST C++ (0) | 2022.02.18 |
| 백준 2887번 : 행성 터널 - 크루스칼 (0) | 2022.02.18 |
| 백준 1197번 : 최소 스패닝 트리 - Kruskal & Prim Algorithm (0) | 2022.02.18 |
| 백준 1854번 : K번째 최단경로 찾기 (0) | 2022.02.18 |
