[백준] 17472번 다리 만들기 2 (C++, 삼성 기출)

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

이 문제도 크루스칼 알고리즘을 공부하기 위해 풀었다.
섬을 구분하기 위해 bfs를 통해 섬 번호를 넣어줬고, 섬에서 이동하며 간선을 구해 vector에 넣어줬다.
크루스칼 알고리즘을 통해 최소 스패닝 트리를 구해 가중치의 합을 출력해주면 된다.
이때, 모든 섬이 연결되어 있는지 확인하기 위해 마지막에 모든 섬의 부모가 같은지 확인해줬다.

해결 과정

1. 입력은 map[i][j] 값이 1일 때, -1로 바꿔 넣어준다.
2. 모든 -1인 점에 대해 bfs를 돌리면서 섬의 번호를 map에 넣어준다.
3. 모든 점에 대해 동, 서, 남, 북으로 움직이면서 다른 섬을 만나면 간선 vector에 넣어준다.
4. 간선의 가중치가 낮은 것 기준으로 sort 해준다.
5. 크루스칼 알고리즘을 통해 다리 길이의 최솟값을 구해준다.
   5-1. union-find를 통해 간선이 연결된 두 정점의 부모를 찾아준다.
   5-2. 부모가 같은 경우, 싸이클이 발생하므로 스킵해준다.
   5-3. 부모가 다른 경우, 가중치를 결과값에 더해주고 더 작은 부모로 대입해준다.
6. 연결이 안된 섬이 있을 수 있으므로, 모든 섬에 대해 부모가 같은지 확인해준다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int map[11][11];
int parent[10];
bool visited[10];
int dir[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
queue<pair<int, int>> q;

struct edge {
public :
	int node[2];
	int dist;
	edge(int a, int b, int dist) {
		this->node[0] = a;
		this->node[1] = b;
		this->dist = dist;
	}
	bool operator <(edge& e) {
		return this->dist < e.dist;
	}
};

vector<edge> v;

void bfs(int x, int y, int num) {
	q.push({ x, y });
	map[y][x] = num;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
			if (map[ny][nx] == -1) {
				map[ny][nx] = num;
				q.push({ nx, ny });
			}
		}
	}
}

void move(int x, int y, int direction) {
	int sum = 0;
	int value = map[y][x];
	int nx = x;
	int ny = y;
	while (1) {
		nx += dir[direction][0];
		ny += dir[direction][1];
		if (nx < 0 || nx >= m || ny < 0 || ny >= n || map[ny][nx] == value) return;
		if (map[ny][nx] == 0)
			sum++;
		else {
			if(sum >= 2)
				v.push_back(edge(value, map[ny][nx], sum));
			return;
		}
	}
}

int get_parent(int a) {
	if (parent[a] == a)	return a;
	else return get_parent(parent[a]);
}

void union_parent(int a, int b) {
	a = get_parent(a);
	b = get_parent(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

bool find(int a, int b) {
	a = get_parent(a);
	b = get_parent(b);
	if (a == b) return true;
	else return false;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++){
			cin >> map[i][j];
			if (map[i][j] == 1)
				map[i][j] = -1;
		}

	int num = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (map[i][j] == -1) {
				bfs(j, i, num);
				num++;
			}
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < 4; k++)
				if (map[i][j] != 0)
					move(j, i, k);

	sort(v.begin(), v.end());

	for (int i = 0; i < 10; i++) {
		parent[i] = i;
	}

	int sum = 0;
	for (int i = 0; i < v.size(); i++) {
		if (!find(v[i].node[0], v[i].node[1])) {
			sum += v[i].dist;
			union_parent(v[i].node[0], v[i].node[1]);
		}
	}

	int p = get_parent(1);
	for (int i = 2; i < num; i++)
		if (p != get_parent(i))
			sum = 0;

	if (sum == 0)
		cout << "-1";
	else
		cout << sum;
}