https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
BFS + MST 로 해결하는 문제입니다.
먼저 섬의 번호를 구분할 수 있게 표시하고,
섬의 한 지점에서 한방향으로 탐색을 하여 길이가 2이상인 다리를 놓을수 있는지 확인합니다.
놓을 수 있으면 시작 섬 번호, 도착 섬 번호, 길이를 벡터에 push_back을 하고,
길이가 2 미만이거나 놓을 수 없으면 빠져나와줍니다.
(여기서 chk 배열을 사용한건
섬 1에서 섬 2까지 연결하는데 같은길이의 다리를 2개 이상 놓을 수 있는 경우와
섬 1에서 섬 2까지 연결하는 것과 섬 2에서 섬 1까지 연결하는 것이 중복되기 때문에 사용하였습니다.)
이제 시작 섬 번호, 도착 섬 번호, 길이 정보가 담겨있는 벡터를 길이가 작은 순서대로 sort를 한 후에
크루스칼 알고리즘에서 작은 간선을 선택하는 방식처럼 작은 길이를 선택해주면서 parent 배열을 갱신합니다.
(parent 배열에는 해당 번호 섬의 root가 되는 섬의 번호가 저장되어 있으며, 어떤 섬과 연결되어 있는지 알 수 있습니다.)
ans가 0이면 -1을 출력하고 끝내면 되고, 아니면 답을 출력하면 되는데
중요한 것은 모든섬을 연결해야 한다는 것입니다. (그거 때문에 왜틀렸는지 오랫동안 고민해서 ㅠㅠ)
섬이 최대 6개이므로 선형으로 root가 같은지 체크를 한 후에 정답을 출력합니다.
|
1 6
1 0 0 1 0 1
//ans : -1
|
문제풀이 하면서 찾은 반례 던지고 갑니다.
[C++]
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct edge {
int s;
int e;
int d;
}edge;
vector<edge> v;
int parent[11], N, M, ans, areadiv;
int list[10][10], direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
bool visit[10][10], chk[10][10][10];
bool cmp(edge a, edge b) {
return a.d < b.d;
}
int find_parent(int u) {
if (parent[u] == u) return u;
return parent[u] = find_parent(parent[u]);
}
void union_find(int a, int b) {
int aroot = find_parent(a);
int broot = find_parent(b);
parent[max(aroot, broot)] = min(aroot, broot);
}
void func() {
for (int i = 0; i < v.size(); i++) {
int s = v[i].s;
int e = v[i].e;
int sroot = find_parent(s);
int eroot = find_parent(e);
if (sroot == eroot) continue;
union_find(sroot, eroot);
ans += v[i].d;
}
if (!ans) {
cout << "-1\n";
return;
}
int root = find_parent(1);
for (int i = 2; i <= areadiv; i++) {
int next = find_parent(i);
if (root != next) {
ans = -1;
break;
}
}
cout << ans << '\n';
}
void dist(int x, int y, int di, int sn) {
int xx = x;
int yy = y;
int cnt = 0;
while (1) {
int nx = xx + direct[di][0];
int ny = yy + direct[di][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) break;
if (list[nx][ny] == sn) break;
if (!list[nx][ny]) {
cnt++;
xx = nx;
yy = ny;
}
else if (list[nx][ny] != sn) {
if (cnt < 2) break;
if (chk[sn][list[nx][ny]][cnt] || chk[list[nx][ny]][sn][cnt]) break;
chk[sn][list[nx][ny]][cnt] = true;
chk[list[nx][ny]][sn][cnt] = true;
v.push_back({ sn, list[nx][ny], cnt });
break;
}
}
return;
}
void find_dist() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j]) {
for (int k = 0; k < 4; k++) {
dist(i, j, k, list[i][j]);
}
}
}
}
sort(v.begin(), v.end(), cmp);
}
void bfs(int sx, int sy, int num) {
queue<pair<int, int> > q;
q.push({ sx,sy });
visit[sx][sy] = true;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
list[x][y] = num;
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (!list[nx][ny] || visit[nx][ny]) continue;
q.push({ nx,ny });
visit[nx][ny] = true;
}
}
}
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> list[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visit[i][j] || !list[i][j]) continue;
bfs(i, j, ++areadiv);
}
}
for (int i = 1; i <= areadiv; i++) {
parent[i] = i;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
find_dist();
func();
return 0;
}
|
cs |
[Java]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static ArrayList<int[]> edge = new ArrayList<>();
static int list[][] = new int[11][11];
static boolean visit[][] = new boolean[11][11];
static boolean chk[][][] = new boolean[7][7][11];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int parent[] = new int[7];
static int N, M, cnt, div, ans;
static int find(int v) {
if (parent[v] == v)
return v;
return parent[v] = find(parent[v]);
}
static void Union(int u, int v, int w) {
int a = find(u);
int b = find(v);
if (a == b)
return;
parent[b] = a;
cnt++;
ans += w;
}
static void solve() {
Collections.sort(edge, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[2] - o2[2];
}
});
for (int i = 0; i < edge.size(); i++) {
int x = edge.get(i)[0];
int y = edge.get(i)[1];
int dis = edge.get(i)[2];
Union(x, y, dis);
}
if (cnt != div - 1)
System.out.println(-1);
else
System.out.println(ans);
}
static void getDist(int sx, int sy, int d, int num) {
int x = sx;
int y = sy;
int cnt = 0;
while (true) {
x += direct[d][0];
y += direct[d][1];
cnt++;
if (x < 1 || y < 1 || x > N || y > M)
break;
if (list[x][y] == num)
break;
if (list[x][y] == 0)
continue;
if (list[x][y] != num) {
if (cnt <= 2)
break;
if (chk[num][list[x][y]][cnt])
break;
chk[num][list[x][y]][cnt] = true;
chk[list[x][y]][num][cnt] = true;
edge.add(new int[] { num, list[x][y], cnt - 1 });
return;
}
}
}
static void dist() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (list[i][j] != 0) {
for (int k = 0; k < 4; k++) {
getDist(i, j, k, list[i][j]);
}
}
}
}
}
static void init() {
for (int i = 1; i <= div; i++) {
parent[i] = i;
}
}
static void bfs(int sx, int sy) {
Deque<int[]> dq = new ArrayDeque<>();
dq.add(new int[] { sx, sy });
visit[sx][sy] = true;
while (!dq.isEmpty()) {
int x = dq.peek()[0];
int y = dq.poll()[1];
list[x][y] = div;
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 1 || ny < 1 || nx > N || ny > M)
continue;
if (visit[nx][ny] || list[nx][ny] == 0)
continue;
dq.add(new int[] { nx, ny });
visit[nx][ny] = true;
}
}
}
static void func() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (visit[i][j] || list[i][j] == 0)
continue;
div++;
bfs(i, j);
}
}
init();
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= M; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
input();
func();
dist();
solve();
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 17142 연구소 3 (0) | 2021.01.22 |
|---|---|
| boj 2636 치즈 (0) | 2021.01.22 |
| boj 1039 교환 (0) | 2021.01.22 |
| boj 3055 탈출 (0) | 2021.01.22 |
| boj 2234 성곽 (0) | 2021.01.22 |