백준 17472번 _ 다리 만들기 2

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

---

코드

#include <iostream>
#include <vector>
#include <algorithm>

#define MAXVAL 987654321

using namespace std;

int N, M;
int board[10][10];
int calBoard[10][10];
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0,0, -1,1 };
int islandDis[7][7];
int numOfIsland = 0;

//유니온 파인드
int parents[7];

void parentsInit()
{
	for (int i = 1; i <= numOfIsland; i++)
		parents[i] = i;
}

int getParent(int a)
{
	if (parents[a] == a) return a;
	return parents[a] = getParent(parents[a]);
}

void Union(int a, int b)
{
	a = getParent(a);
	b = getParent(b);
	parents[b] = a;
}

void islandDisInit()
{
	for (int i = 1; i <= 6; i++)
	{
		for (int j = 1; j <= 6; j++)
		{
			islandDis[i][j] = MAXVAL;
		}
	}
}

void printIslandDis()
{
	for (int i = 1; i <= 6; i++)
	{
		for (int j = 1; j <= 6; j++)
		{
			if (islandDis[i][j] == MAXVAL)
				continue;

			cout << i << " - > " << j << " : " << islandDis[i][j] << endl;
		}
	}
}

void PrintBindIsland()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cout << calBoard[i][j] << ' ';
		}
		cout << endl;
	}
}

void Input()
{
	cin >> N >> M;

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

bool IsInRange(int y, int x)
{
	if (y >= 0 && y < N && x >= 0 && x < M)
		return true;
	return false;
}

void Dfs(int y, int x, int islandNumber)
{
	if (IsInRange(y, x) == false)
		return;

	if (board[y][x] != 1)
		return;

	if (calBoard[y][x] != 0)
		return;

	calBoard[y][x] = islandNumber;

	for (int i = 0; i < 4; i++)
		Dfs(y + dy[i], x + dx[i], islandNumber);
}

void BindIsland()
{
	//섬끼리 묶어놓음
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] != 1)
				continue;

			if (calBoard[i][j] != 0)
				continue;

			numOfIsland++;
			Dfs(i, j, numOfIsland);
		}
	}
}

void MakeBridge()
{
	// ->
	for (int i = 0; i < N; i++)
	{
		int s = -1, e = -1, length = 0;
		for (int j = 0; j < M; j++)
		{
			if (calBoard[i][j] != 0)
			{
				if (s == -1)
				{
					length = 0;
					s = calBoard[i][j];
				}
				//이땐 다리임
				else
				{
					if (s == calBoard[i][j])
					{
						length = 0;
						continue;
					}

					e = calBoard[i][j];
					if (length > 1)
					{
						islandDis[s][e] = min(islandDis[s][e], length);
						islandDis[e][s] = min(islandDis[e][s], length);
					}
					s = e;
					e = -1;
					length = 0;
				}
			}
			//빈공간인 경우
			else
			{
				if (s != -1)
					length++;
			}
		}
	}

	// |
	// v
	for (int j = 0; j < M; j++)
	{
		int s = -1, e = -1, length = 0;
		for (int i = 0; i < N; i++)
		{
			if (calBoard[i][j] != 0)
			{
				if (s == -1)
				{
					length = 0;
					s = calBoard[i][j];
				}
				//이땐 다리임
				else
				{
					if (s == calBoard[i][j])
					{
						length = 0;
						continue;
					}
					e = calBoard[i][j];
					if (length > 1)
					{
						islandDis[s][e] = min(islandDis[s][e], length);
						islandDis[e][s] = min(islandDis[e][s], length);
					}
					s = e;
					e = -1;
					length = 0;
				}
			}
			//빈공간인 경우
			else
			{
				if (s != -1)
					length++;
			}
		}
	}


}

int main()
{
	Input();
	islandDisInit();
	BindIsland();

	//간선들중 최솟값 다 구하기
	MakeBridge();

	//연결 후보군을 만든다. -> next permulate로 돌림
	vector<pair<int, int>> candidate;
	for (int i = 1; i <= numOfIsland; i++)
	{
		for (int j = i + 1; j <= numOfIsland; j++)
		{
			//다리를 건설할수 없는거임
			if (islandDis[i][j] == MAXVAL)
				continue;

			candidate.push_back(make_pair(i, j));
		}
	}

	//이제 전체를 돌리면서 최솟값 구해보자
	int answer = MAXVAL;
	vector<int> temp;
	temp.resize(candidate.size());

	for (int i = 0; i < candidate.size(); i++)
		temp[i] = i;
	sort(begin(temp), end(temp));

	//printIslandDis();
	//PrintBindIsland();

	do
	{
		int num = 0;
		parentsInit();

		for (int i = 0; i < temp.size(); i++)
		{
			int order = temp[i];
			//union find
			if (getParent(candidate[order].first) == getParent(candidate[order].second))
				continue;
			Union(candidate[order].first, candidate[order].second);

			num += islandDis[candidate[order].first][candidate[order].second];
		}
		//전체가 다 연결되었는지 확인
		bool isConnect = true;
		for (int i = 2; i <= numOfIsland; i++)
		{
			if (getParent(1) != getParent(i))
			{
				isConnect = false;
				break;
			}
		}
		if (isConnect == true)
			answer = min(answer, num);
	} while (next_permutation(begin(temp), end(temp)));

	if (answer == MAXVAL)
		cout << -1 << '\n';
	else
		cout << answer << '\n';

	return 0;
}

---

섬은 그룹화 (dfs이용) -> 간선 만들기 -> 유니온 파인드이용