문제 URL : https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
문제 접근법 :
결론부터말하자면 구현+(dfs or bfs) + MST 문제입니다.
문제가 좀어려웠습니다. 처음 해당 섬들의 번호를 부여해야합니다.
dfs 혹은 bfs로 섬번호를 부여합니다.
그리고 해당 섬들로 좌우상하로 일직선으로 바깥으로 나가거나 다른섬을 만날때까지 길이를 재봅니다.
자기자신을 만나면 그냥 탈출해도 좋습니다. 다음 위치에서 다시 시작하면되니까
전부 길이를 쟀을때 가장 작은 길이를 저장해주 십니다.
그리고 마지막으로 해당섬에서 다른섬까지의 거리를 다 측정했다면
크루스칼 알고리즘을 이용해 MST를 만들어주면 됩니다.
쉽게 정리하면
1. 섬번호 부여 (dfs)
2. 섬들간의 거리재기
3. MST (크루스칼 알고리즘이용)
소스코드 :
|
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
|
//By 콩순이냉장고
#include<bits/stdc++.h> using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
vvi board, check, dist;
vi parent;
v<tuple<int, int, int>> dv;
int n, m;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void input() {
cin >> n >> m;
check = board = vvi(n, vi(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
}
int find(int idx) {
if (parent[idx] == idx)
return idx;
return parent[idx] = find(parent[idx]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b)return;
if (a < b)parent[b] = a;
else parent[a] = b;
}
bool isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < m;
}
void dfs(int y, int x, int color) {
if (!isrange(y, x))return;
if (check[y][x] || !board[y][x])return;
board[y][x] = check[y][x] = color;
for (int i = 0; i < 4; i++)
dfs(y + dy[i], x + dx[i], color);
}
void initDist() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int island = board[i][j];
if (!island)continue;
//해당섬이라면 좌우상하 끝가지가서 거리재기
for (int k = 0; k < 4; k++) {
int len = 0;
int y = i + dy[k];
int x = j + dx[k];
while (isrange(y, x)) {
//길을 만들수있으면 길만들기
if (board[y][x] == 0) {
len++;
y += dy[k];
x += dx[k];
}
else {
//다른섬일때
if (board[y][x] != island && len >= 2) {
dist[island][board[y][x]] = dist[board[y][x]][island] = min(dist[island][board[y][x]] = dist[board[y][x]][island], len);
}
break;
}
}
}
}
}
}
int kruskal(int color) {
priority_queue<tuple<int, int, int>> pq;
for (int i = 1; i <= color; i++) {
for (int j = 1; j <= color; j++) {
if (i == j || dist[i][j] >= 1e5)continue;
pq.push({ -dist[i][j],i,j });
}
}
int sum = 0;
while (!pq.empty()) {
int length, num1, num2;
tie(length, num1, num2) = pq.top();
length = -length;
pq.pop();
num1 = find(num1);
num2 = find(num2);
if (num1 != num2) {
sum += length;
merge(num1, num2);
}
}
for (int i = 1; i <= color; i++) {
if (find(parent[1]) != find(parent[i]))return -1;
}
return sum >= 1e5 ? -1 : sum;
}
void solve() {
int color = 0;
//섬번호 부여
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] && check[i][j] == 0)
dfs(i, j, ++color);
}
}
parent = vi(color + 1);
for (int i = 0; i < parent.size(); i++)
parent[i] = i;
dist = vvi(color + 1, vi(color + 1, 1e5));
//섬간의 거리재기
initDist();
//크루스칼 이용
cout << kruskal(color) << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 12852 1로 만들기 2 (0) | 2022.07.13 |
|---|---|
| 백준 16637 괄호 추가하기 (0) | 2022.05.17 |
| 백준 16437 양 구출 작전 (0) | 2022.05.17 |
| 백준 2688 줄어들지 않아 (0) | 2022.04.07 |
| 백준 1103 게임 (0) | 2022.04.07 |
