<백준> 17472

다리 만들기2

입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

출력
모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

BFS로 섬을 찾고 브루트포스를 사용해 다리를 만들고 마지막에 MST로 연결하는 무려 3개의 알고리즘이 들어간 문제이다.

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
typedef tuple<int, int, int> edge;
vector<int> parent;
int visited[101][101] = { false };
vector<pair<int, int>> mlist;
vector<vector<pair<int, int>>> sumlist;
int mapp[101][101];
int n, m, sNum;
priority_queue<edge, vector<edge>, greater<edge>> q;

int find(int a)
{
	if (a == parent[a])
		return a;
	else
		return parent[a] = find(parent[a]);
}

void Union(int a, int b)
{
	a = find(a);
	b = find(b);

	if (a != b)
		parent[b] = a;
}

void BFS(int i, int j)
{
	queue<pair<int, int>> queue;
	queue.push({ i, j });
	mlist.push_back({ i,j });
	visited[i][j] = true;
	mapp[i][j] = sNum;

	while (!queue.empty())
	{
		int r = queue.front().first;
		int c = queue.front().second;
		queue.pop();

		for (int d = 0; d < 4; d++)
		{
			int nx =r+ dx[d];
			int ny = c+dy[d];

			if (nx >= 0 && nx < n && ny >= 0 && ny < m)
			{
				if (!visited[nx][ny] && mapp[nx][ny] != 0)
				{
					visited[nx][ny] = true;
					mapp[nx][ny] = sNum;
					queue.push({ nx,ny });
					mlist.push_back({ nx,ny });

				}
			}
		}
	}
}

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

	cin >> n >> m;

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

	sNum = 1;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (mapp[i][j] != 0 && visited[i][j] != true)
			{
				mlist.clear();
				BFS(i, j);
				sNum++;
				sumlist.push_back(mlist);
			}
		}
	}

	for (int i = 0; i < sumlist.size(); i++)
	{
		vector<pair<int, int>> now = sumlist[i];

		for (int j = 0; j < now.size(); j++)
		{
			int r = now[j].first;
			int c = now[j].second;
			int now_s = mapp[r][c];

			for (int d = 0; d < 4; d++)
			{
				int tempX = r+dx[d];
				int tempY = c+dy[d];
				int blength = 0;

				while (true)
				{
					if (tempX < 0 || tempX >= n || tempY < 0 || tempY >= m)
						break;
					if (mapp[tempX][tempY] == now_s)
						break;
					else if (mapp[tempX][tempY] != 0)
					{
						if (blength > 1)
							q.push(edge{ blength, now_s,mapp[tempX][tempY] });
						break;
					}
					blength++;
					tempX += dx[d];
					tempY += dy[d];
				}
			}
		}
	}
	parent.resize(sNum);

	for (int i = 0; i < parent.size(); i++)
		parent[i] = i;
	int useEdge = 0;
	int result = 0;

	while (!q.empty())
	{
		edge now = q.top();
		q.pop();

		if (find(get<1>(now)) != find(get<2>(now)))
		{
			Union(get<1>(now), get<2>(now));
			result = result + get<0>(now);
			useEdge++;
		}
	}

	if (useEdge == sNum - 2)
		cout << result << "\n";
	else
		cout << -1 << "\n";
}

int dr[] = { -1,0,1,0 };
int dc[] = { 0,1,0,-1 };
int board[101][101];
bool visited[101][101] = { false };
int n, m, num;
vector<vector<pair<int, int>>> sumlist;
vector<pair<int, int>> mlist;
vector<int> parent;
typedef pair<int, pair<int, int>> edge;
priority_queue<edge, vector<edge>, greater<edge>> pq;

int find(int a)
{
	if (a == parent[a])
		return a;
	else
		return parent[a] = find(parent[a]);
}

void Union(int a, int b)
{
	a = find(a);
	b = find(b);

	if (a != b)
		parent[b] = a;
}

void BFS(int a, int b)
{
	queue<pair<int, int>> q;
	mlist.clear();
	q.push({ a,b });
	mlist.push_back({ a,b });
	visited[a][b] = true;
	board[a][b] = num;

	while (!q.empty())
	{
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++)
		{
			int tempR = dr[d];
			int tempC = dc[d];

			while (r + tempR >= 0 && r + tempR < n && c + tempC >= 0 && c + tempC < m)
			{
				if (visited[r + tempR][c + tempC] == false && board[r + tempR][c + tempC] != 0)
				{
					int nowi = r + tempR;
					int nowj = c + tempC;
					board[nowi][nowj] = num;
					visited[nowi][nowj] = true;
					mlist.push_back({ nowi,nowj });
					q.push({ nowi,nowj });
				}
				else
					break;
				if (tempR < 0)
					tempR--;
				else if (tempR > 0)
					tempR++;
				else if (tempC < 0)
					tempC--;
				else if (tempC > 0)
					tempC++;
			}
		}
	}
}

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

	cin >> n >> m;

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

	num = 1;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] != 0 && visited[i][j] != true)
			{
				BFS(i, j);
				num++;
				sumlist.push_back(mlist);
			}
		}
	}
	for (int i = 0; i < sumlist.size(); i++)
	{
		vector<pair<int, int>> now = sumlist[i];

		for (int j = 0; j < now.size(); j++)
		{
			int r = now[j].first;
			int c = now[j].second;
			int nows = board[r][c];

			for (int d = 0; d < 4; d++)
			{
				int tempR = dr[d];
				int tempC = dc[d];
				int length = 0;

				while (r + tempR >= 0 && r + tempR < n && c + tempC >= 0 && c + tempC < m)
				{
					if (board[r + tempR][c + tempC] == nows)
						break;
					else if (board[r + tempR][c + tempC] != 0)
					{
						if (length > 1)
							pq.push({ length,{nows, board[r + tempR][c + tempC]} });
						break;
					}
					else
						length++;
					if (tempR < 0)
						tempR--;
					else if (tempR > 0)
						tempR++;
					else if (tempC < 0)
						tempC--;
					else if (tempC > 0)
						tempC++;
				}
			}
		}
	}
	parent.resize(num);

	for (int i = 0; i < parent.size(); i++)
		parent[i] = i;
	int useEdge = 0;
	int result = 0;

	while (!pq.empty())
	{
		edge now = pq.top();
		pq.pop();
		int v = now.first;
		int s = now.second.first;
		int e = now.second.second;

		if (find(s) != find(e))
		{
			Union(s, e);
			result += v;
			useEdge++;
		}
	}
	if (useEdge == num - 2)
		cout << result << "\n";
	else
		cout << -1 << "\n";
}