백준 17472번 다리 만들기 2 문제 풀이

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

17472번: 다리 만들기 2

 

백준저지 17472번 문제 다리 만들기 2문제입니다.

 

N, M이 10으로 크지 않고 섬의 개수도 6개 밖에 안되므로, 하나하나씩 직접 찾아가도 크게 문제가 없습니다.

 

대충 단계는 다음과 같습니다.

 

1. Flood Fill로 모든 섬 찾기

2. 다리를 놓을 수 있는 모든 경우를 체크 함

3. 섬을 Graph의 Vertex로, 다리를 놓는 경우를 Edge로 모델링함

4. 그래프에 대한 최소 스패닝 트리(MST: Minimum Spanning Tree)를 구한다.

5. MST의 길이를 리턴, MST를 구할 수 없는 경우 -1를 리턴.

 

1번은 재귀를 이용한 dfs로 간단하게 짯으며(find_island 함수), 하는 과정에 물과 맞닿아 있는 좌표는 별도로 표기를 했습니다.

 

2번은 try_bridge 함수에서 체크를 했고, 한쪽 방향으로 계속 전진하며 다른 섬을 만나거나 맵 밖으로 나갈때까지 전진한 뒤 다리의 조건이 되는지를 체크했습니다.

 

4번은 MST를 크루스칼 알고리즘을 이용해서 구했습니다. Edge를 가장 짧은 길이순으로 소팅한 뒤, 하나씩 포함할 것인지 아닌지를 DSU(Disjoint Set 혹은 Union Find 자료구조)로 체크하면서 합쳤습니다.

 

 

코드입니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int N, M;
int field[11][11];

#define NOT_FOUND -1
#define WATER 0
//섬은 1~6의 숫자 값을 갖는다.
struct Pos {
	int x, y;
};
struct Bridge {
	int src, dest, len;
	bool operator<(const struct Bridge& rhs) const {
		return len < rhs.len;
	}
};
bool isin(Pos p) {
	return p.x >= 0 && p.y >= 0 && p.x < N && p.y < M;
}
struct Island {
	vector<Pos> edge; //물과 맞닿아있는 지점 좌표(다리 지을 수 있는지 체크용)
};
vector<Bridge> bridges;
Island islands[7];
const Pos d[4] = { {0, +1}, {+1, 0}, {-1, 0}, {0, -1} };
void find_island(Pos pos, int id) {
	field[pos.x][pos.y] = id;
	int water = 0;
	for (int k = 0; k < 4; k++) {
		Pos nx = { pos.x + d[k].x, pos.y + d[k].y };
		if (isin(nx)) {
			if (field[nx.x][nx.y] == NOT_FOUND) {
				find_island(nx, id);
			}
			else if (field[nx.x][nx.y] == WATER) {
				water++;
			}
		}
	}
	if (water) {
		islands[id].edge.push_back(pos);
	}
}
void try_bridge(const Pos pos) {
	const int id = field[pos.x][pos.y];
	for (int k = 0; k < 4; k++) {
		Pos p = { pos.x + d[k].x, pos.y + d[k].y };
		int len = 0;
		int dest = 0;
		while (isin(p) && field[p.x][p.y] == 0) {
			p.x += d[k].x;
			p.y += d[k].y;
			len++;
		}
		if (isin(p)) {
			dest = field[p.x][p.y];
		}
		if (len >= 2 && dest) {
			bridges.push_back({ id, dest, len });
		}
	}
}
int dsu[7];
int dsu_find(int p) {
	while (dsu[p] != p) {
		p = dsu[p];
	}
	return p;
}
int main() {
	int island_cnt = 1;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> field[i][j];
			if (field[i][j]) field[i][j] = -1;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (field[i][j] == NOT_FOUND) {
				dsu[island_cnt] = island_cnt;
				find_island({ i, j }, island_cnt++);
			}
		}
	}
	for (int i = 1; i < island_cnt; i++) {
		for (Pos p : islands[i].edge) {
			try_bridge(p);
		}
	}

	// 최소 스패닝 트리 만들기
	sort(bridges.begin(), bridges.end());
	int total_len = 0;
	for (auto b : bridges) {

		if (dsu_find(b.src) != dsu_find(b.dest)) {
			total_len += b.len;
			// Disjoint Set Merge
			dsu[dsu_find(b.src)] = dsu_find(b.dest);
		}
	}

	// 최소 스패닝 트리에 모든 섬이 포함되었는지 확인
	int dsu_first = dsu_find(1);
	for (int i = 2; i < island_cnt; i++) {
		if (dsu_first != dsu_find(i)) {
			total_len = -1;
		}
	}
	cout << total_len << endl;
	return 0;
}