[C++] 백준 17472 : 다리 만들기 2

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

17472번: 다리 만들기 2

백준 17472번 다리 만들기 2 를 풀었다.

 

문제에서 모든 섬을 연결하는 최소 비용을 구하라고 해서 최소 스패닝 트리로 풀어야 겠다고 생각했다.

문제를 풀기 전에 아래와 같이 생각하고 구현을 시작했다.

1. 섬에 번호를 매긴다.

2. 섬과 섬 사이에 놓을 수 있는 다리를 찾는다.

3. 크루스칼 알고리즘으로 최소 비용을 찾는다.

 

먼저 섬을 입력받은 후 섬마다 번호를 매겼다.

번호를 매긴 이유는 시작섬과 도착섬의 숫자가 달라야 섬의 구분이 가능해서 크루스칼 알고리즘에 필요한 Edge에 넣을 수 있기 때문이다.

 

아래는 입력받은 섬의 위치다.

0	0	0	0	0	0	1	1
1	1	0	0	0	0	1	1
1	1	0	0	0	0	0	0
1	1	0	0	0	1	1	0
0	0	0	0	0	1	1	0
0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1

 

아래가 섬에 번호를 매긴 새로운 map배열이다.

0	0	0	0	0	0	1	1
2	2	0	0	0	0	1	1
2	2	0	0	0	0	0	0
2	2	0	0	0	3	3	0
0	0	0	0	0	3	3	0
0	0	0	0	0	0	0	0
4	4	4	4	4	4	4	4

 

섬의 번호를 매긴 후 섬과 섬 사이에 놓을 수 있는 다리를 찾았다. 모든 섬의 좌표가 있는 island 벡터를 순회하면서 각 좌표마다 다른 섬과 연결 가능한 다리를 찾았다.

 

Edge에 모든 간선이 들어간 상태고, 크루스칼 알고리즘을 사용해서 최소 비용을 구하면 된다. 다만 주의해야할 점은 모든 섬이 연결되었는지 확인을 해야 한다는 것이다.

크루스칼 알고리즘을 수행하면서 최소 비용을 계산하는데 사용한 간선의 시작섬과 도착섬을 connect_check벡터에 넣었다. 크루스칼이 끝나면 connect_check벡터에는 섬이 어떻게 연결되었는지 알 수 있는 그래프 정보가 담기게 된다.

그 그래프를 DFS로 확인해서 모든 섬이 연결되어있는지 체크하면 된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#pragma warning(disable:4996)

using namespace std;
#define INF 1234567890
struct Edge {
	int start;
	int end;
	int cost;
	Edge(){}
	Edge(int X, int Y, int Z) : start(X), end(Y), cost(Z) {}
};
struct compare {
	bool operator()(Edge a, Edge b) {
		return a.cost > b.cost;
	}
};

int n, m;
int island_id = 1;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int map[10][10];
int new_map[10][10];
int visited[10][10];
vector<pair<int,int>> island;
vector<int> connect_check[7];
int visited_check[7];

priority_queue<Edge, vector<Edge>, compare> pq;
int parent[7];
int MST_cost;

int find_parent(int x) {
	if (parent[x] == x)
		return x;
	return parent[x] = find_parent(parent[x]);
}

void union_parent(int x, int y) {
	int x_p = find_parent(x);
	int y_p = find_parent(y);
	if (parent[x_p] < parent[y_p])
		parent[y_p] = parent[x_p];
	else
		parent[x_p] = parent[y_p];
}

bool isCycle(int x, int y) {
	int x_p = find_parent(x);
	int y_p = find_parent(y);
	if (x_p == y_p)
		return 1;
	else
		return 0;
}

void Kruskal() {
	for (int i = 0; i < 8; i++) {
		parent[i] = i;
	}
	while (!pq.empty()) {
		Edge temp = pq.top();
		int start = temp.start;
		int end = temp.end;
		int cost = temp.cost;
		pq.pop();
		if (isCycle(start, end) == 0) {
			MST_cost += cost;
			connect_check[start].push_back(end);
			connect_check[end].push_back(start);
			union_parent(start, end);
		}
	}
}

void find_island(int start_id, int dir, int x, int y) {
	int next_x = x;
	int next_y = y;
	int dist = 1;
	while (1) {			
		next_x = next_x + dx[dir];
		next_y = next_y + dy[dir];
		if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m) {
			if (new_map[next_x][next_y] == 0) {
				// keep find
				dist++;
			}
			else {
				int start = start_id;
				int end = new_map[next_x][next_y];
				int cost = dist;
				if (cost >= 2) {
					pq.push(Edge(start, end, cost));
				}
				break;
			}
		}
		else {
			break;
		}	
	}
}

void check_edge(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];
		int direction = i;
		if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m) {
			if (new_map[next_x][next_y] == 0) {
				find_island(new_map[x][y], direction, next_x, next_y);
			}
		}
	}
}

void DFS(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];
		if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m) {
			if (visited[next_x][next_y] == 0 && map[next_x][next_y] == 1) {
				visited[next_x][next_y] = 1;
				new_map[next_x][next_y] = island_id;
				DFS(next_x, next_y);
			}
		}
	}
}

void DFS(int x) {
	visited_check[x] = 1;
	for (int i = 0; i < connect_check[x].size(); i++) {
		int next_x = connect_check[x][i];
		if (visited_check[next_x] == 0) {
			DFS(next_x);
		}
	}
}

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] != 0)
				island.push_back({ i,j });
		}
	}

	for (int i = 0; i < island.size(); i++) {
		int x = island[i].first;
		int y = island[i].second;
		if (visited[x][y] == 0) {
			new_map[x][y] = island_id;
			DFS(x, y);
			island_id++;
		}
	}

	for (int i = 0; i < island.size(); i++) {
		int x = island[i].first;
		int y = island[i].second;
		check_edge(x, y);
	}

	Kruskal();

	DFS(1);

	for (int i = 1; i < island_id; i++) {
		if (visited_check[i] == 0) {
			cout << -1;
			return 0;
		}
	}

	cout << MST_cost;

	return 0;
}