[BOJ] #17472 _ 다리 만들기 2

[다리 만들기 2] https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

map의 정보를 0과 1로만 준다.

따라서, 바다를 각 숫자로 만들어주고, 최단 거리를 구한 후, 모두 연결되어 있는지 확인하였다.

 

getNewMap() 함수를 통해 아래와 같이 바다를 각 숫자로 변경해주었다.

 

getDistMap() 함수를 통해 각 바다의 거리를 구해주었다.

 

최단거리를 구하고, 모두 연결되어 있는지 확인하기 위해 크루스칼 알고리즘을 사용하였다.

 

크루스칼 알고리즘 (Kruskal's Algorithm) 이란?
가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘

[참고] https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#define MAX 10
#define INF 99999999

using namespace std;
typedef struct sea {
	int a, b, d;
}Sea;

int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 };
int N, M, island_cnt;
int map[MAX][MAX], new_map[MAX][MAX], dist[7][7], chk[7];
vector<pair<int, int> > island[6];

void initDist();
int solve();
void getNewMap();
void getDistMap();
int getMinDist();
int findParent(int idx);
int checkConnect();
bool cmp(const Sea& a, const Sea& b);
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	printf("%d\n", solve());

	return 0;
}

void initDist() {
	for (int i = 0; i < 7; i++) {
		for (int j = 0; j < 7; j++) dist[i][j] = INF;
	}
}

int solve() {
	initDist();
	getNewMap();
	getDistMap();
	return getMinDist();
}

void getNewMap() {
	queue<pair<int, int> > q;
	int check[MAX][MAX] = { 0, }, tmp_y, tmp_x, y, x;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j]) {
				if (check[i][j]) continue;
				q.push(make_pair(i, j));
				island[island_cnt].push_back(make_pair(i, j));
				new_map[i][j] = island_cnt + 1;
				check[i][j] = 1;

				while (!q.empty()) {
					y = q.front().first;
					x = q.front().second;
					q.pop();

					for (int k = 0; k < 4; k++) {
						tmp_y = y + dy[k];
						tmp_x = x + dx[k];
						if (tmp_x < 0 || tmp_y < 0 || tmp_x >= M || tmp_y >= N) continue;
						if (check[tmp_y][tmp_x]) continue;
						if (!map[tmp_y][tmp_x]) continue;
						q.push(make_pair(tmp_y, tmp_x));
						island[island_cnt].push_back(make_pair(tmp_y, tmp_x));
						new_map[tmp_y][tmp_x] = island_cnt + 1;
						check[tmp_y][tmp_x] = 1;
					}
				}
				island_cnt++;
			}
		}
	}
}

void getDistMap() {
	int d, tmp_y, tmp_x, val;

	for (int i = 0; i < island_cnt; i++) {
		for (int j = 0; j < island[i].size(); j++) {
			tmp_y = island[i][j].first;
			tmp_x = island[i][j].second;
			val = new_map[island[i][j].first][island[i][j].second];
			for (int k = 0; k < 4; k++) {
				d = 0;
				while (1) {
					tmp_y += dy[k];
					tmp_x += dx[k];
					if (tmp_y < 0 || tmp_x < 0 || tmp_y >= N || tmp_x >= M) break;
					if (new_map[tmp_y][tmp_x] == val) break;
					if (new_map[tmp_y][tmp_x] > 0) {
						if (d == 1) break;
						dist[val][new_map[tmp_y][tmp_x]] = min(dist[val][new_map[tmp_y][tmp_x]], d);
						dist[new_map[tmp_y][tmp_x]][val] = dist[val][new_map[tmp_y][tmp_x]];
						break;
					}
					d++;
				}
			}
			
		}
	}
}

int getMinDist() {
	vector<Sea> v;

	for (int i = 1; i <= island_cnt; i++) {
		chk[i] = i;
		for (int j = i + 1; j <= island_cnt; j++) {
			if (dist[i][j] == INF) continue;
			v.push_back({ i,j,dist[i][j] });
		}
	}
	sort(v.begin(), v.end(), cmp);

	int result = 0, tmp_a, tmp_b;
	for (int i = 0; i < v.size(); i++) {
		tmp_a = findParent(v[i].a);
		tmp_b = findParent(v[i].b);
		if (tmp_a == tmp_b) continue;
		result += v[i].d;
		chk[tmp_b] = tmp_a;
	}

	if (checkConnect()) return result;
	else return -1;
}

int findParent(int idx) {
	while (idx != chk[idx]) idx = chk[idx];
	return idx;
}

int checkConnect() {
	int cmp_val = findParent(chk[1]);
	for (int i = 2; i <= island_cnt; i++) {
		if (findParent(i) != cmp_val) return 0;
	}
	return 1;
}

bool cmp(const Sea& a, const Sea& b) {
	return a.d < b.d;
}