[C/C++] 백준 - 17472번 : 다리 만들기2 (크루스칼 알고리즘)

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

17472번: 다리 만들기 2

문제

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다. 

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다리의 총 길이: 13 D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다.	다리의 총 길이: 9 (최소)

다음은 올바르지 않은 3가지 방법이다

C의 방향이 중간에 바뀌었다	D의 길이가 1이다.	가로 다리인 A가 1과 가로로 연결되어 있지 않다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

A의 길이는 4이고, B의 길이도 4이다. 총 다리의 총 길이: 4 + 4 + 2 = 10	다리 A: 2와 3을 연결 (길이 2) 다리 B: 3과 4를 연결 (길이 3) 다리 C: 2와 5를 연결 (길이 5) 다리 D: 1과 2를 연결 (길이 2) 총 길이: 12

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

출력

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

 

이 문제를 처음 봤을 때는 BFS 또는 DFS로 해결하면 되려나 생각했는데,

생각해보니 각 육지가 하나의 노드가 되고 육지들을 잇는 다리가 간선이라고 하면 각 노드를 연결시켜주는 간선의 최소값을 구하는 문제라는 것을 깨달았다. 그래서 크루스칼 알고리즘을 이용하면 해결 가능할 거라고 판단이 들었고, 크루스칼 알고리즘을 써서 AC를 받을 수 있었다.

 

크루스칼은 기본적으로 Union_Find 알고리즘과 우선순위 큐를 사용하기 때문에 이 부분은 인지하고 있어야한다.

우선순위 큐에는 간선의 길이, 이어지는 2개의 육지 번호를 저장하는 구조체를 하나 생성해주었다.

그래서 간선의 길이를 기준으로 하는 최소힙으로 정렬해주었다.

< 알고리즘 순서 >

1. 처음에 육지가 모두 1로 초기화 되어있기 때문에 BFS를 통해 붙어있는 육지를 하나로 묶어주어 다른 수로 표시해주는 넘버링 과정을 해준다. Union-Find를 편리하게 사용하기 위해

 

2. 각 육지들 간에 떨어진 거리를 구해준다. 이 부분은 DFS를 통해 직선 거리만 구할 수 있도록 해준다.

→ 위 2가지를 거치면 각 육지간 떨어진 거리와 두 개의 육지 정보가 우선순위 큐에 모두 담겨있다.

 

3. 이제 우선순위 큐에서 하나씩 꺼내 육지를 연결시켜준다. 최소힙 구조이기 때문에 간선의 길이가 짧은거부터 연결시켜준다. 우선순위 큐에서 꺼낸 정보 육지1과 육지2가 이미 연결되어있다면 진행하지 않고 연결이 아직 안되어있다면 답으로 출력할 Answer변수에 간선의 길이를 추가해주고 Union함수를 통해 2개의 육지를 연결시켜준다.

위 과정을 우선순위 큐가 빌 때까지 진행해준다.

 

4. 우선순위 큐에 담긴 정보를 모두 꺼내 위 과정을 거친 후에도 각 육지의 대표값이 모두 같지 않다면 다리를 통해 모두 연결이 불가능하다는 뜻이므로 Answer를 -1로 초기화시켜준다.

#include<iostream>
#include<cmath>
#include<list>
#include<stack>
#include<tuple>
#include<map>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX_SIZE 1003
#define INF 987654321
using namespace std;
typedef long long ll;
typedef struct Information {
	int Len;
	int n1;
	int n2;
}Information;

struct cmp {
	bool operator()(Information A, Information B) {
		return A.Len > B.Len;
	}
};

int N, M, go;
int board[102][102];
int visited[102][102];
int Parent[7];
bool isLink[7][7];

const int dy[] = { 1,-1,0,0 };
const int dx[] = { 0,0,1,-1 };
priority_queue<Information, vector<Information>, cmp> pq;
vector<pair<int, int>> Land[7];

bool isValid(int y, int x) {
	return (0 <= y && y < N && 0 <= x && x < M);
}

void Input_Data() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
		}
	}
}

int getParent(int x) {
	if (x == Parent[x]) return x;
	return Parent[x] = getParent(Parent[x]);
}

void Union(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	
	if (a < b) {
		for (int i = 1; i <= go; i++) {
			if (Parent[i] == b) Parent[i] = a;
		}
	}	
	else {
		for (int i = 1; i <= go; i++) {
			if (Parent[i] == a) Parent[i] = b;
		}
	}
}

bool isSameParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);

	if (a == b) return true;
	return false;
}

void Numbering() {
	go = 0;
	queue<pair<int, int>> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 1 && !visited[i][j]) {
				++go;
				q.push({ i,j });
				visited[i][j] = true;
				board[i][j] = go;
				Land[go].push_back({ i,j });

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

					for (int dir = 0; dir < 4; dir++) {
						int ny = y + dy[dir];
						int nx = x + dx[dir];
						
						if (!isValid(ny, nx) || visited[ny][nx]) continue;
						if (board[ny][nx] == 1) {
							board[ny][nx] = go;
							Land[go].push_back({ ny, nx });
							q.push({ ny, nx });
							visited[ny][nx] = true;
						}
					}
				}
			}
		}
	}
}

void DFS(int y, int x, int d, int Number, int len) {
	int ny = y + dy[d];
	int nx = x + dx[d];
	if (isValid(ny, nx)) {
		if (board[ny][nx] == 0) DFS(ny, nx, d, Number, len+1);
		else if (board[ny][nx] != 0 && board[ny][nx] != Number) {
			pq.push({ len, Number, board[ny][nx] });
		}
	}
}

void Go_Length() {
	for (int i = 1; i <= go; i++) {
		for (int l = 0; l < Land[i].size(); l++) {
			int y = Land[i][l].first;
			int x = Land[i][l].second;

			for (int dir = 0; dir < 4; dir++) {
				int ny = y + dy[dir];
				int nx = x + dx[dir];

				if (isValid(ny, nx) && board[ny][nx] == 0) {
					DFS(ny, nx, dir, i, 1);
				}
			}
		}
	}
}

void Init_Parent() {
	for (int i = 1; i <= go; i++) Parent[i] = i; 
}

void MST() {
	int Answer = 0;
	while (!pq.empty()) {
		Information Temp = pq.top();
		pq.pop();
		if (Temp.Len < 2) continue;
		if (isSameParent(Temp.n1, Temp.n2)) continue;
		Answer += Temp.Len;
		Union(Temp.n1, Temp.n2);
	}

	for (int i = 2; i <= go; i++) {
		if (Parent[i] != Parent[i - 1]) Answer = -1;
	}
	cout << Answer << endl;
}

int main() {
	CUNLINK;
	Input_Data();
	Numbering();
	Go_Length();
	Init_Parent();
	MST();

	return 0;
}