백준17472 다리 만들기2

작성일 | In

문제 링크

  • http://icpc.me/17472

사용 알고리즘

  • MST
  • 브루트 포스

풀이

삼성 코테 기출이라 그런지 제 코드를 읽는 사람이 정말 많습니다.

BFS등의 알고리즘으로 각 섬을 분리해주고, 섬들을 이어주는 간선들을 만들어준 다음에 MST를 구해주면 됩니다.

코드를 설명하자면…
Edge구조체는 이름 그대로 간선을 표현하는 구조체입니다.
bfs(i, j, k)는 (i, j)와 같은 섬에 있는 모든 셀들을 구해서 k번째 섬이라고 라벨을 붙여줍니다.
f(i, j, dir)은 (i, j)에서 시작해 dir 방향으로 뻗어가면서 처음으로 만나는 섬과 다리로 이어줍니다.
find/merge함수는 기본적인 union-find 연산을 담당하는 함수입니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef pair<int, int> p;

struct Edge{
	int s, e, x;
	Edge(){}
	Edge(int s, int e, int x) : s(s), e(e), x(x) {}
	bool operator < (const Edge &t) const {
		return x < t.x;
	}
};

const int di[] = {1, -1, 0, 0};
const int dj[] = {0, 0, 1, -1};

int n, m;
int inp[11][11];
int arr[11][11];
vector<Edge> edge;
vector<p> v[11];

bool bound(int i, int j){
	return 1 <= i && i <= n && 1 <= j && j <= m;
}

void bfs(int i, int j, int k){
	queue<p> q; q.push({i, j});
	arr[i][j] = k;
	v[k].push_back({i, j});
	while(q.size()){
		i = q.front().x;
		j = q.front().y;
		q.pop();
		for(int x=0; x<4; x++){
			int ii = i + di[x];
			int jj = j + dj[x];
			if(!bound(ii, jj)) continue;
			if(!inp[ii][jj] || arr[ii][jj]) continue;
			arr[ii][jj] = k;
			v[k].push_back({ii, jj});
			q.push({ii, jj});
		}
	}
}

void f(int i, int j, int dir){
	int s = arr[i][j];
	int cnt = 0;
	while(1){
		i += di[dir];
		j += dj[dir];
		cnt++;
		if(!bound(i, j) || arr[i][j] == s) break;
		if(!arr[i][j]) continue;
		if(cnt-1 != 1) edge.push_back({s, arr[i][j], cnt-1});
		break;
	}
}

int par[11];
int find(int v){
	return v == par[v] ? v : par[v] = find(par[v]);
}
bool merge(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return 0;
	par[u] = v;
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	int pv = 0;
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> inp[i][j];
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(!arr[i][j] && inp[i][j]) bfs(i, j, ++pv);

	for(int i=1; i<=pv; i++){
		for(auto t : v[i]){
			for(int d=0; d<4; d++) f(t.x, t.y, d);
		}
	}

	sort(all(edge));
	int ans = 0, cnt = 0;
	for(int i=0; i<11; i++) par[i] = i;
	for(auto i : edge){
		int s = i.s, e = i.e, x = i.x;
		if(merge(s, e)) ans += x, cnt++;
	}
	if(cnt != pv-1) cout << -1;
	else cout << ans;
}