BOJ 백준 17472 다리 만들기 2

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

17472번: 다리 만들기 2

문제 풀이)

 

    1. bfs를 통해 섬들의 정보(좌표)를 저장한다.

    2. 각각 섬들 간에 다리를 놓을 수 있는 최소 거리를 저장한 배열을 만들어준다.

    3. 크루스칼 알고리즘을 이용하여 최소 비용 신장 트리(MST)를 만들어준다.

 

cf) 크루스칼 알고리즘 - 비용이 가장 작은 간선부터 선택해가는 알고리즘

 

    2번을 거치게 되면 모든 섬들 간의 다리에 대한 정보가 배열에 저장된다.

    섬들 간의 다리의 정보는 ( 섬1, 섬2, 다리의 비용 ) 으로 이루어져 있다.

    이 배열을 다리의 비용을 기준으로 낮은 순서로 정렬해준다.

    비용이 낮은 다리부터 선택하되, 사이클(Cycle)이 일어나는지 확인한다.

 

cf) 사이클

a, b, c 의 세 개의 섬이 있을 때, a - b, b - c, c - a 와 같이 연결되어 있으면 사이클이 발생했다고 한다.

만약 c - a의 다리를 끊으면 사이클이 발생하지 않는다.

 

사이클이 일어나는 지 확인하는 알고리즘은 Union-Find가 있다.

 

cf) Union-Find

각 노드의 부모 노드를 보고, 부모 노드가 다르다면 두 개의 노드를 합쳐주는 알고리즘이다.

GetParent() 함수를 통해 노드의 부모를 찾고, 그 둘이 다르다면 Union을 통해 합쳐준다.

 

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

#define SIZE 15
#define ISLAND_SIZE 10
#define INF 999999999

typedef vector<pair<int, int>> ISLAND;
struct ISLAND_RELATION
{
	ISLAND_RELATION(int _to, int _from, int _cost)
		: to(_to), from(_from), cost(_cost) {}

	int to, from, cost;

	bool operator < (const ISLAND_RELATION& stIR)
	{ return cost < stIR.cost; }
};

int dirX[4] = { 0, 0, 1, -1 };
int dirY[4] = { 1, -1, 0, 0 };

int g_n, g_m;
int g_nCost;
int arrMap[SIZE][SIZE] = { 0 };

vector<ISLAND>				vecIslands;
vector<ISLAND_RELATION>		vecIRs;

void Input()
{
	scanf("%d %d", &g_n, &g_m);
	for (int i = 0; i < g_n; ++i)
	{
		for (int j = 0; j < g_m; ++j)
		{
			scanf("%d", &arrMap[i][j]);
		}
	}
}

// 한 개의 섬을 찾아 저장
bool bVisit[SIZE][SIZE] = { false };
void FindIsland(int x, int y)
{
	ISLAND vecIsland;
	queue<pair<int, int>> q;
	q.push({ x, y });
	bVisit[x][y] = true;
	vecIsland.push_back({ x, y });

	while (!q.empty())
	{
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int next_x = cur_x + dirX[i];
			int next_y = cur_y + dirY[i];

			if (next_x < 0 || next_y < 0 || next_x >= g_n || next_y >= g_m)
				continue;
			else if (!arrMap[next_x][next_y])
				continue;
			else if (bVisit[next_x][next_y])
				continue;

			q.push({ next_x, next_y });
			bVisit[next_x][next_y] = true;
			vecIsland.push_back({ next_x, next_y });
		}
	}

	vecIslands.push_back(vecIsland);
}

// 섬들을 찾아 저장하기
void SetIslands()
{
	for (int i = 0; i < g_n; ++i)
	{
		for (int j = 0; j < g_m; ++j)
		{
			if (arrMap[i][j] && !bVisit[i][j])
				FindIsland(i, j);
		}
	}
}

// 두 섬 간의 다리 길이를 계산
int CalcBridgeLegnth(pair<int, int>& a, pair<int, int>& b)
{
	int nLen = INF;
	int left, right;
	bool bPath;
	// 같은 행에 있는 경우
	if (a.first == b.first)
	{
		left = a.second < b.second ? a.second : b.second;
		right = a.second > b.second ? a.second : b.second;
		left++;

		bPath = true;
		for (int i = left; i < right; ++i)
		{
			if (arrMap[a.first][i])
			{
				bPath = false;
				break;
			}
		}

		int diff = right - left;
		if (bPath && diff > 1 && nLen > diff)
			nLen = right - left;
	}

	if (a.second == b.second)
	{
		left = a.first < b.first ? a.first : b.first;
		right = a.first > b.first ? a.first : b.first;
		left++;

		bPath = true;
		for (int i = left; i < right; ++i)
		{
			if (arrMap[i][a.second])
			{
				bPath = false;
				break;
			}
		}

		int diff = right - left;
		if (bPath && diff > 1 && nLen > diff)
			nLen = right - left;
	}

	return nLen;
}

// 각 섬들 간에 다리를 놓을 수 있는지 조사
void SetIslandsRelation()
{
	for (int i = 0; i < vecIslands.size() - 1; ++i)
	{
		for (int j = i + 1; j < vecIslands.size(); ++j)
		{
			ISLAND a = vecIslands[i];
			ISLAND b = vecIslands[j];
			
			// a섬과 b섬을 잇는 다리의 최소 개수를 저장하기
			int bridgeCnt = INF;
			for (int i = 0; i < a.size(); ++i)
			{
				for (int j = 0; j < b.size(); ++j)
				{
					int diff = CalcBridgeLegnth(a[i], b[j]);
					if (diff < bridgeCnt)
						bridgeCnt = diff;
				}
			}

			if (bridgeCnt != INF && bridgeCnt != 1)
			{
				ISLAND_RELATION stIR(i, j, bridgeCnt);
				vecIRs.push_back(stIR);
			}
		}
	}

	sort(begin(vecIRs), end(vecIRs));
}

int arrParents[ISLAND_SIZE] = { 0 };
int GetParent(int x)
{
	if (arrParents[x] == x)
		return x;
	return GetParent(arrParents[x]);
}

void Union(int island_1, int island_2)
{
	int x = GetParent(island_1);
	int y = GetParent(island_2);

	if (x < y)
		arrParents[y] = x;
	else
		arrParents[x] = y;
}

int Kruskal()
{
	// 각각의 노드의 부모를 자신으로 설정
	for (int i = 0; i < ISLAND_SIZE; ++i)
		arrParents[i] = i;

	int nCost = 0;
	for (int i = 0; i < vecIRs.size(); ++i)
	{
		ISLAND_RELATION ir = vecIRs[i];
		if (GetParent(ir.from) != GetParent(ir.to))
		{
			nCost += ir.cost;
			Union(ir.from, ir.to);
		}
	}
	return nCost;
}

void Solution()
{
	SetIslands();				// 섬 찾기
	SetIslandsRelation();		// 섬 간의 다리 놓기
	g_nCost = Kruskal();		// 크루스칼 알고리즘으로 최소 비용 찾기
}

void PrintResult()
{
	// 모든 노드의 부모가 같은지, 즉 모든 섬이 연결되어 있는지 확인
	bool bSuccess = true;
	for (int i = 0; i < vecIslands.size() - 1; ++i)
	{
		if (GetParent(i) != GetParent(i + 1))
		{
			bSuccess = false;
			break;
		}
	}

	if (bSuccess)
		printf("%d\n", g_nCost);
	else
		printf("-1\n");
}

int main()
{
	Input();
	Solution();
	PrintResult();

 	return 0;
}