191019 백준 알고리즘 문제풀기*

#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAX_ISLAND 7

struct bridge_info
{
	int from, to, length;
};

int map[11][11];
int num_map[11][11];
int check[11][11];
int connect[MAX_ISLAND][MAX_ISLAND];
int parent[MAX_ISLAND];

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };


vector<pair<int,int>> islands;
vector<bridge_info> bridges;

void make_num(int H, int W)
{
	int num_island = 1;
	for (int i = 0; i<int(islands.size()); i++)
	{
		int cx = islands[i].first;
		int cy = islands[i].second;
		if (num_map[cy][cx] != 0) continue;
		queue<pair<int, int>> q;
		num_map[cy][cx] = num_island;
		q.push(make_pair(cx, cy));
		while (!q.empty())
		{
			cx = q.front().first;
			cy = q.front().second;
			q.pop();
			for (int k = 0; k < 4; k++)
			{
				int nx = cx + dx[k];
				int ny = cy + dy[k];
				if (nx < 0 || W <= nx || ny < 0 || H <= ny) continue;
				if (num_map[ny][nx] != 0) continue;
				if (map[ny][nx] != 1) continue;
				num_map[ny][nx] = num_island;
				q.push(make_pair(nx, ny));
			}
		}
		num_island++;
	}
}

void make_connection(int from, int to, int dist)
{
	int cur_length = connect[from][to];
	if (cur_length == 0)
	{//첫 연결이라면 그냥 연결하고
		connect[from][to] = dist;
		connect[to][from] = dist;
	}
	else
	{//첫 연결이 아니라면 대소비교를 해서 최솟값만 연결한다.
		if (dist < cur_length)
		{//만약 계산된 값이 현재 길이보다 짧다면
			connect[from][to] = dist;
			connect[to][from] = dist;
		}
	}
}

void go(int x, int y, int dir, int W, int H)
{
	memset(&check, 0, sizeof(check));
	int cur_num = num_map[y][x];
	int other_num = -1;
	int bridge_size = -1;
	int cx = x;
	int cy = y;
	check[cy][cx] = 1;
	int sx = x; // 시작 좌표 만들기
	int sy = y;
	while (1)
	{
		int bx = cx; //이전 좌표 만들기
		int by = cy;
		cx += dx[dir];//다음 좌표 만들기
		cy += dy[dir];

		if (cx < 0 || W <= cx || cy < 0 || H <= cy)
		{
			break; // 범위벗어나면 break
		}
		if ((num_map[cy][cx] != 0) && (num_map[cy][cx] == num_map[sy][sx]))
		{
			break; //다리 못 놓고 이전과 같은 섬이여도 break
		}

		check[cy][cx] = check[by][bx] + 1;

    if (num_map[cy][cx] != 0 && num_map[cy][cx] != cur_num)
		{//만약 다른 섬을 만났다면
			other_num = num_map[cy][cx];
			bridge_size = check[by][bx] - 1;
			break;
		}
	}

	if (other_num == -1 || bridge_size <= 1)
	{//해당 방향으로 만들어진 다리로 다른 섬을 찾지 못한 경우
	// 또는 다리 길이가 1인 경우
		return; // 그냥 종료
	}
	else
	{//해당 방향으로 만들어진 다리로 다른 섬을 찾은 경우
		make_connection(cur_num, other_num, bridge_size); // 연결을 만든다.
	}
}

//정렬 함수
bool Compare(const bridge_info &x, const bridge_info &y)
{
	return x.length < y.length;
}
int find(int u)
{
	if (parent[u] == u) return u;
	else return parent[u] = find(parent[u]);
}
void merge(int u, int v)
{
	u = find(u);
	v = find(v);

	if (u == v) return;
	parent[u] = v;
}
void make_bridges(int H, int W)
{
	for (int j = 0; j < H; j++)
	{
		for (int i = 0; i < W; i++)
		{
			if (num_map[j][i] == 0) continue;
			for (int k = 0; k < 4; k++)
			{
				go(i, j, k, W, H);
			}
		}
	}

	//printf("made connections\n");
	//for (int j = 1; j < MAX_ISLAND; j++)
	//{
	//	for (int i = 1; i < MAX_ISLAND; i++)
	//	{
	//		printf("%2d", connect[j][i]);
	//	}
	//	printf("\n");
	//}
	int last_idx = 0;

	//connection 맵에서 모두 연결되는 최소 거리 고르기
	//우선 bridges info 만들기
	for (int j = 1; j < MAX_ISLAND; j++)
	{
		for (int i = 1; i < j; i++)
		{
			if (connect[j][i] == 0) continue;
			bridges.push_back({ j,i,connect[j][i] });
			if (last_idx < j) last_idx = j;
		}
	}
  
	//sort(0번부터 from to length로 연결정보 저장됨
	sort(bridges.begin(), bridges.end(), Compare);
	
	//부모 초기화
	for (int j = 1; j < MAX_ISLAND; j++)
	{
		parent[j] = j;
	}
	int res = 0;
	for (int i = 0; i < bridges.size(); i++)
	{
		if(find(bridges[i].from)!=find(bridges[i].to))
		{
			res += bridges[i].length;

			merge(bridges[i].from, bridges[i].to);
		}
	}

	//부모 한번 더 맞춰주기
	for (int i = 0; i < bridges.size(); i++)
	{
		if (find(bridges[i].from) != find(bridges[i].to))
		{
			merge(bridges[i].from, bridges[i].to);
		}
	}

	/*for (int i = 1; i <= last_idx; i++)
	{
		find(i);
	}*/

	int parent_ = parent[1];
	bool diff_parent = false;
	for (int i = 2; i < last_idx; i++)
	{
		if (parent_ != parent[i]) diff_parent = true;
	}
	if (diff_parent) res = 0;
	if (res == 0) res = -1;
	printf("%d\n", res);
	
}

int main()
{
	int N, M; // H=N, W=M
	scanf("%d %d", &N, &M);
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < M; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] != 0)
			{
				islands.push_back(make_pair(i,j));
			}
		}
	}

	//섬 번호 붙이기
	make_num(N, M);

	//printf("made nums\n");
	//for (int j = 0; j < N; j++)
	//{
	//	for (int i = 0; i < M; i++)
	//	{
	//		printf("%2d", num_map[j][i]);
	//	}
	//	printf("\n");
	//}

	//다리 연결하기
	make_bridges(N, M);

	std::system("pause");
	return 0;
}