[백준] 다리 만들기 2

정태호·2022년 11월 25일
0

N x M 의 이차원 공간에서 섬은 1로 바다는 0으로 표시되는 정보를 바탕으로 섬간에 가장 짧은 거리의 다리를 두어 모든 섬을 이동할 수 있도록 해야하는 문제이다.

A -> B -> C 로 연결되어 있다면 A -> C 가 성립되고 이때 최소비용을 통해 다리를 연결해야한다.

먼저 BFS 탐색을 통해 해당 섬들의 마킹번호를 부여 하였다.
그런 후 순차적으로 해당 블럭을 확인하며 섬간의 직선상 거리정보를 수집했다.(이때 거리가 1이하는 무시)

수집한 모든 간선정보를 직선거리 정보를 기준으로 오름차순으로 정렬한다. 그런 후 순차적으로 탐색하며, 유니온 파인드 알고리즘을 통해 가장 적은 비용으로 모든 섬을 연결할 수 있다

#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

#define MAX 9

int N, M;
int dp[MAX];
int metrix[100][100];

int sft[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };

struct S {
	int x;
	int y;
};

bool cmp(vector<int>& a, vector<int>& b) {
	return a[2] < b[2];
}

void fill_area(int x, int y, int num) {
	queue<S> q;
	q.push({ x, y });

	while (q.size()) {
		auto set = q.front();
		q.pop();

		metrix[set.x][set.y] = num;

		for (int i = 0; i < 4; i++) {
			int set_x = set.x + sft[i][0];
			int set_y = set.y + sft[i][1];
			if (set_x >= 0 && set_y >= 0 && set_x < N && set_y < M && metrix[set_x][set_y] == 1) {
				q.push({ set_x,set_y });
			}
		}
	}
}

int find(int n) {
	if (dp[n] == 0)
		return n;
	return dp[n] = find(dp[n]);
}


int main() {
	vector<vector<int>> buf;

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> metrix[i][k];
		}
	}

	int count = 2;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (metrix[i][k] == 1) fill_area(i, k, count++);
		}
	}


	for (int i = 0; i < N; i++) {
		int first = 0;
		int count = 0;
		for (int k = 0; k < M; k++) {
			if (metrix[i][k] > 1 && first == 0) first = metrix[i][k];  // 섬위치일 경우 첫 섬미등록시
			else if (metrix[i][k] == first) count = 0; // 첫번째 섬을 밟고 있는경우 count 초기화
			else if (metrix[i][k] > 1) { // 첫번째 섬이 아닌 다른섬을 밟았을 경우
				if (count > 1) {
					buf.push_back({ first,metrix[i][k],count });// 그 거리가 2이상일 경우 노드를 추가
				}
				count = 0;
				first = metrix[i][k];
			}
			else if (first != 0) count++;
		}
	}

	for (int i = 0; i < M; i++) {
		int first = 0;
		int count = 0;
		for (int k = 0; k < N; k++) {
			if (metrix[k][i] > 1 && first == 0) first = metrix[k][i];  // 섬위치일 경우 첫 섬미등록시
			else if (metrix[k][i] == first) count = 0; // 첫번째 섬을 밟고 있는경우 count 초기화
			else if (metrix[k][i] > 1) { // 첫번째 섬이 아닌 다른섬을 밟았을 경우
				if (count > 1) {
					buf.push_back({ first,metrix[k][i],count });// 그 거리가 2이상일 경우 노드를 추가
				}
				count = 0;
				first = metrix[k][i];
			}
			else if (first != 0) count++;
		}
	}

	sort(buf.begin(), buf.end(), cmp);

	int result = 0;
	for (auto& b : buf) {
		int A = find(b[0]);
		int B = find(b[1]);

		if (A != B) { //연결되어 있지 않은 경우
			dp[A] = B;
			result += b[2];
		}
	}

	int check = 0;
	for (int i = 2; i < count; i++) {
		if (dp[i] == 0) check++;
	}
	if (check == 1)
		cout << result;
	else
		cout << -1;

}

0개의 댓글