17472 다리 만들기 2

정답 코드를 보아도 이해가 안된 문제였다.. 접근의 핵심은 모든 섬을 연결했을 때의 최소 거리이며, 이 부분에서 MST가 생각나지 않았다.

처음 시도는 dfs로 모든 섬을 연결할 수 있는지 판단하면 어떨까 했는데 연결 부분에서 막혔다.

서론은 여기까지 하고 문제를 분석해보면 접근 방법은 다음과 같다.

1. 각각의 섬을 구분해주기 위해 BFS 혹은 DFS로 넘버링한다.

    1.1 여기서 섬을 넘버링 해주는 이유는 뒤에 나올 크루스칼 알고리즘을 사용하기 위함이다.

2. 반복문으로 1인 칸마다 연결할 수 있는 다리를 각 방향마다 계산하여 벡터에 저장한다.

3. 2에서 구한 다리들을 가지고, 크루스칼 알고리즘을 수행한다.

    3.1 수행하면서 다리를 놓을 때의 길이를 답에 더한다.

 

고찰 : 내가 생각하지 못했던 점은 2번과 3번이다. 빈 칸을 기준으로 상하좌우로 다리를 놓는단 생각으로 접근하려니 구현이 너무 까다로워졌다. 또한 최소의 비용으로 그래프의 노드들을 연결하는 최소 비용 신장 트리의 개념을 잘 이해하지 못하여 바로 떠올리지 못했다.

정답코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int Height, Width;
int arr[11][11];
int visit[11][11];
int dirRow[] = { 1, 0, -1, 0 };
int dirCol[] = { 0, 1, 0, -1 };
struct bridge {
	int from_row, from_col;
	int to_row, to_col;
	int dist;
};
struct island {
	int r, c;
	int num;
};
vector<bridge> bridges;
int parents[101];

bool cmp(bridge& b1, bridge& b2)
{
	return b1.dist < b2.dist;
}
bool IsRange(int nr, int nc)
{
	if (nr >= 0 && nc >= 0 && nr < Height && nc < Width)
		return true;
	return false;
}
vector<bridge> make_bridge(int row, int col)
{
	bridge b;
	vector<bridge> result;
	int nr, nc, dist = 0;
	for (int dir = 0; dir < 4; dir++) {
		dist = 1;
		while (1) {
			nr = row + dirRow[dir] * dist;
			nc = col + dirCol[dir] * dist;
			if (!IsRange(nr, nc))
				break;
			if (arr[nr][nc] == 1) {
				if (dist > 2) {
					b = { row, col, nr, nc, dist - 1 };
					result.push_back(b);
				}
				break;
			}
			dist++;
		}
	}
	return result;
}
bool find_island(int row, int col, int number)
{
	island la = { row, col, number };
	queue<island> q;
	q.push(la);
	visit[row][col] = number;
	int r, c, nr, nc, n;
	while (!q.empty()) {
		r = q.front().r;
		c = q.front().c;
		n = q.front().num;
		q.pop();
		auto brs = make_bridge(r, c);
		for (const auto& b : brs)
			bridges.push_back(b);

		for (int i = 0; i < 4; i++) {
			nr = r + dirRow[i];
			nc = c + dirCol[i];
			if (nr < 0 || nc < 0 || nr >= Height || nc >= Width)
				continue;
			if (arr[nr][nc] == 1 && visit[nr][nc] == 0) {
				visit[nr][nc] = n;
				la = { nr, nc, n };
				q.push(la);
			}
		}
	}
	return true;
}
int get_parent(int x)
{
	if (parents[x] == x)
		return x;
	return parents[x] = get_parent(parents[x]);
}
void union_parent(int a, int b)
{
	a = get_parent(a);
	b = get_parent(b);
	if (a < b) 
		parents[b] = a;
	else
		parents[a] = b;
}
int find(int a, int b)
{
	a = get_parent(a);
	b = get_parent(b);
	if (a == b)
		return 1;
	else
		return 0;
}
int main()
{
	cin >> Height >> Width;
	for (int r = 0; r < Height; r++)
		for (int c = 0; c < Width; c++)
			cin >> arr[r][c];
	for (int i = 0; i < 101; i++)
		parents[i] = i;
	int number = 1;
	for (int r = 0; r < Height; r++) {
		for (int c = 0; c < Width; c++) {
			if (arr[r][c] == 1 && visit[r][c] == 0) {
				find_island(r, c, number++);
			}
		}
	}
	sort(bridges.begin(), bridges.end(), cmp);
	int answer = 0;
	for (int i = 0; i < bridges.size(); i++) {
		auto &b = bridges[i];
		int fr, fc, tr, tc;
		fr = b.from_row, fc = b.from_col;
		tr = b.to_row, tc = b.to_col;
		if (!find(visit[fr][fc], visit[tr][tc])) {
			union_parent(visit[fr][fc], visit[tr][tc]);
			answer += b.dist;
		}
	}
	int island_number = get_parent(1);
	for (int i = 2; i < number; i++) {
		if (island_number != get_parent(i)) {
			printf("-1\n");
			return 0;
		}
	}
	printf("%d\n", answer);
	return 0;
}