백준 17472 다리만들기 2 - 최소스패닝트리(크루스칼) , BFS , C++

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

문제풀이

 

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;
}

백준 17472번