백준 / 17472 다리 만들기 2 C++

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

삼성 A형 기출 문제입니. 뭔가 어렵지 않게 풀 수 있을 거라 생각했지만 역시 삼성 기출문제답게 구현이 빡셌습니다. 

이 문제의 핵심 알고리즘은 MST (최소 신장 트리) 입니다. 최소신장트리는 크루스칼 알고리즘이나 프림 알고리즘을 이용해 구할 수 있는데 크루스칼 알고리즘을 이용해 구현했습니다.

 

문제 해결 과정은 다음과 같습니다.

 

1. 입력을 받는다.

2. 입력으로 들어온 애들 중 같은 섬인 것의 좌표를 묶는다. (bfs를 이용해 섬을 만들었습니다.)

3. 각 섬에 대해 다른 섬까지의 최소 거리를 구한다. (바다와 맞닿은 섬의 좌표들에 대해 다른 섬의 바다와 맞닿은 좌표의 거리를 비교하면 됩니다. 문제에서 직선만 허용하므로 상하좌우 4가지 경우에 대해 모두 계산합니다.)

4. 위 과정을 마치면 가중치가 있는 간선을 가지는 그래프를 얻을 수 있습니다. (섬 : 노드, 거리 : 가중치 간선)

5. 크루스칼 알고리즘을 이용해 최소신장트리를 구하면 됩니다.

 

크루스칼 알고리즘은 다음과 같습니다.

1. 각 가중치를 기준으로 오름차순으로 정렬한다.

2. 정렬된 순으로 노드를 연결한다.

3. 노드를 연결했을 때 사이클이 생기면 해당 노드는 연결하면 안 된다. (유니온 파인드로 사이클 유무 판단)

4. 위를 간선이 n-1개 (노드 n개) 가 될 때까지 2,3번을 반복한다.

 

해당 문제에서는 모든 섬끼리 연결되는 경우가 없다면 -1을 출력하라고 하였으므로, 크루스칼 알고리즘을 적용하였을 때, 간선이 n-1개가 되지 않는다면 모든 섬을 연결하는 경우는 없는 것입니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

int n, m;
bool map[11][11]; // false : 바다, true : 섬
vector<vector<pair<int, int>>>land; // 각 섬의 위치 기록
int dist[7][7];
int *parent;

void make_map()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
}

// 섬 구하기
void find_land()
{
	int dy[4] = { 0,0,-1,1 };
	int dx[4] = { 1,-1,0,0 };
	bool visited[11][11];
	memset(visited, false, sizeof(visited));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			
			if (map[i][j] && !visited[i][j]) {
				queue<pair<int, int>>q;
				q.push({ i,j });
				vector<pair<int, int>>v;

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

					visited[y][x] = true;
					v.push_back({ y,x });

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

						if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
							if (map[ny][nx] && !visited[ny][nx]) {
								q.push({ ny,nx });
							}
						}
					}
				}

				land.push_back(v);
				v.clear();
			}
		}
	}
}

// 최소 신장 트리 이용
// 크루스칼 이용
// 먼저 각 섬끼리 연결한 간선의 가중치 중 최솟값을 구한 뒤
// 크루스칼 알고리즘을 이용해 최소신장트리를 구한다.
// 그러면 그것이 답으로 예상

// p,q 사이에 바다만 존재해야함
bool only_sea(pair<int, int>p, pair<int, int>q)
{
	bool no_land = true;

	if (p.first == q.first) {
		if (p.second > q.second) {
			for (int i = q.second + 1; i < p.second; i++)
				if (map[p.first][i]) {
					no_land = false;
					break;
				}
		}

		else {
			for(int i=p.second+1;i<q.second;i++)
				if (map[p.first][i]) {
					no_land = false;
					break;
				}
		}
	}

	else {
		if (p.first > q.first) {
			for (int i = q.first + 1; i < p.first; i++)
				if (map[i][p.second]) {
					no_land = false;
					break;
				}
		}

		else {
			for (int i = p.first + 1; i < q.first; i++)
				if (map[i][p.second]) {
					no_land = false;
					break;
				}
		}
	}

	return no_land;
}

// 각 노드 별 이동 최소 거리 구하기
void cal_dist(int from, int to) // from,to:섬 번호
{
	vector<pair<int, int>>v1 = land[from];
	vector<pair<int, int>>v2 = land[to];
	int d = 987654321;

	for (int i = 0; i < v1.size(); i++) {

		for (int j = 0; j < v2.size(); j++) {

			pair<int, int>p1 = v1[i];
			pair<int, int>p2 = v2[j];

			// 위로 연결 가능할 때
			if ((p1.first - 1 >= 0) && (p1.first - 1 < n) && !map[p1.first - 1][p1.second]) {
				if ((p1.second == p2.second) && (p2.first + 1 >= 0) && (p2.first + 1 < n) && !map[p2.first + 1][p2.second]) {
					if ((p1.first - p2.first - 1) >= 2 && only_sea(p1, p2)) {
						d = min(d, p1.first - p2.first - 1);
					}
				}
			}

			// 아래로 연결 가능할 때
			if ((p1.first + 1 >= 0) && (p1.first + 1 < n) && !map[p1.first + 1][p1.second]) {
				if ((p1.second == p2.second) && (p2.first - 1 >= 0) && (p2.first - 1 < n) && !map[p2.first - 1][p2.second]) {
					if ((p2.first - p1.first - 1) >= 2 && only_sea(p1, p2)) {
						d = min(d, p2.first - p1.first - 1);
					}
				}
			}

			// 좌로 연결 가능할 때
			if ((p1.second - 1 >= 0) && (p1.second - 1 < m) && !map[p1.first][p1.second - 1]) {
				if ((p1.first == p2.first) && (p2.second + 1 >= 0) && (p2.second + 1 < m) && !map[p2.first][p2.second + 1]) {
					if ((p1.second - p2.second - 1) >= 2 && only_sea(p1, p2)) {
						d = min(d, p1.second - p2.second - 1);
					}
				}
			}

			// 우로 연결 가능할 때
			if ((p1.second + 1 >= 0) && (p1.second + 1 < m) && !map[p1.first][p1.second + 1]) {
				if ((p1.first == p2.first) && (p2.second - 1 >= 0) && (p2.second - 1 < m) && !map[p2.first][p2.second - 1]) {
					if ((p2.second - p1.second - 1) >= 2 && only_sea(p1, p2)) {
						d = min(d, p2.second - p1.second - 1);
					}
				}
			}
		}
	}

	if (d == 987654321) {
		dist[from][to] = 0;
		dist[to][from] = 0;
	}
	else {
		dist[from][to] = d;
		dist[to][from] = d;
	}
}

// 유니온 파인드에 쓸 함수들
void init_parent()
{
	int size = land.size();
	parent = (int*)malloc(sizeof(int) * size);
	for (int i = 0; i < size; i++)
		parent[i] = i;
}

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

bool cycle(int node1, int node2)
{
	node1 = find_parent(node1);
	node2 = find_parent(node2);
	if (node1 == node2)
		return true;
	else
		return false;
}

void union_parent(int node1, int node2)
{
	// 부모 노드가 작은 값에 연결
	node1 = find_parent(node1);
	node2 = find_parent(node2);
	if (node1 < node2)
		parent[node2] = node1;
	else
		parent[node1] = node2;
}

int main()
{
	make_map();
	find_land();

	// 크루스칼 알고리즘
	// vec : 거리, {from, to}
	int land_size = land.size();
	vector<pair<int, pair<int, int>>>vec; 
	for (int i = 0; i < land_size; i++) {
		for (int j = i + 1; j < land_size; j++) {
			if (dist[i][j] != 0)
				continue;
			cal_dist(i, j);
			if(dist[i][j]!=0)
				vec.push_back({ dist[i][j],{i,j} });
		}
	}

	sort(vec.begin(), vec.end());
	int result = 0;
	int edge = 0;

	// 유니온 파인드로 사이클 유무 확인
	init_parent();
	for (int i = 0; i < vec.size(); i++) {
		bool cycle_check = cycle(vec[i].second.first, vec[i].second.second);
		if (!cycle_check) {
			result += vec[i].first;
			union_parent(vec[i].second.first, vec[i].second.second);
			edge++;
		}
	}

	// 트리 유무 확인
	if (land_size - 1 == edge)
		cout << result;
	else
		cout << -1;
}