[백준/BOJ] 백준 17472번 : 다리 만들기 2

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

17472번: 다리 만들기 2

섬 사이의 길이를 구하고 최소 스패닝 트리를 만드는 방식으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int n, m;
vector<vector<int>> board(10, vector<int>(10));
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
vector<pair<int, pair<int, int>>> edge; //(길이, (섬1, 섬2))
vector<vector<int>> edge_len(101, vector<int>(101)); //[섬1][섬2] = 섬1, 섬2의 길이
vector<int> parent(101);
vector<int> rank_size(101);
int number = 0;

void Pre()
{
	for (int i = 1; i <= 100; i++)
	{
		parent[i] = i;
		rank_size[i] = 1;
		for (int j = 1; j <= 100; j++)
		{
			edge_len[i][j] = 987654321;
		}
	}
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

	if (rank_size[u] < rank_size[v])
	{
		parent[u] = v;
	}

	else
	{
		parent[v] = u;

		if (rank_size[u] == rank_size[v])
			rank_size[u]++;
	}

}

//섬의 번호를 체크
void Check_island(pair<int, int> here, int number)
{
	board[here.first][here.second] = number;

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] == -1)
		{
			Check_island(there, number);
		}
	}
}

int Find_island(pair<int, int> here, int dir, int& len)
{
	//범위를 벗어낫을때
	if (here.first < 0 || here.second < 0 || here.first >= n || here.second >= m)
		return -1;

	//섬을 찾았을때
	if (board[here.first][here.second] != 0)
		return board[here.first][here.second];

	pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);
	len++;

	return Find_island(there, dir, len);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			int input;
			cin >> input;

			if (input == 1)
				input = -1; //땅은 일단 -1로 표시

			board[i][j] = input;
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] == -1)
			{
				number++; //섬의 번호
				Check_island(make_pair(i, j), number); //섬의 번호를 표시(섬의 번호는 1부터 시작한다)
			}

		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			//섬 일때
			if (board[i][j] != 0)
			{
				pair<int, int> here = make_pair(i, j);

				for (int k = 0; k < 4; k++)
				{
					pair<int, int> there = make_pair(here.first + dxdy[k][0], here.second + dxdy[k][1]);

					//there가 바다 방향일때
					if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] == 0)
					{
						int len = 0;
						int find_island = Find_island(there, k, len);

						//현재 섬과 다른 섬을 찾았고 섬사이의 길이가 2이상일때
						if (find_island != -1 && board[here.first][here.second] != find_island && len >= 2)
						{
							//해당 섬들 사이의 길이가 더 작은것을 찾았을때 갱신한다
							if (edge_len[min(board[here.first][here.second], find_island)][max(board[here.first][here.second], find_island)] > len)
							{
								edge_len[min(board[here.first][here.second], find_island)][max(board[here.first][here.second], find_island)] = len;
							}
						}

					}
				}
			}
		}

	for (int i = 1; i <= number; i++)
		for (int j = 1; j <= number; j++)
		{
			//연결된 섬일때
			if (edge_len[i][j] != 987654321)
				edge.push_back(make_pair(edge_len[i][j], make_pair(i, j)));
		}

	//최소 스패닝을 만드는 방식
	int result = 0;
	int cnt = 0;
	sort(edge.begin(), edge.end()); //길이가 짧은 것 순으로 정렬
	for (int i = 0; i < edge.size(); i++)
	{
		int this_len = edge[i].first;
		int u = edge[i].second.first;
		int v = edge[i].second.second;

		if (Find(u) != Find(v))
		{
			result += this_len;
			cnt++;

			Merge(u, v);
		}
	}

	//최소 스패닝 트리를 만들 수 없을때(최소 스패팅 트리의 edge개수는 정점의 개수-1)
	if (cnt != number - 1)
		result = -1;

	cout << result;

	return 0;
}