[백준 17472] 다리만들기 2 와 mst에 대한 설명

이 문제가 삼성 코테에 기출 되어서 풀어봤는데, 여러가지 알고리즘이 한 문제에 누적 되어 있어, 풀어보면
좋을 것 같아 자잘한 설명과 함께 코드를 공유하려합니다! 코드에 대한 설명은 주석으로 상세하게 적어놨습니다~

 

문제를 처음보면, 딱 "그룹" 이라는 단어가 떠오르면서 자연스럽게 mst(최소 스패닝 트리) 에 관한 문제인 것을 캐치하고

풀어 나갔다. 

 

MST에 대해 잘 모른다면, 아래의 글을 참고하자.

https://codenme.tistory.com/manage/posts/

Tistory

문제는 크게 3파트로 나눌 수 있는데

1) 각 섬에 번호를 붙여 저장하기 (섬간의 구분을 위해) 
이건 bfs를 통해 구현했다..

2)섬간의 거리를 구한다.
이것 역시 bfs 를 통해, 각섬의 모든 요소들에서 도착 섬까지의 최단 거리를 구하고, 그중 가장 짧은 거리를 최단거리로 저장했다.

3)위의 1,2 단계는 각각 정점(섬),  가중치(섬간의 거리)를 구한 것이다. 이 정보를 통해, MST(최소 스패닝 트리) 를 만들어주면
최소 비용으로 모든 섬을 연결할 수 있다. 크루스칼(비용이 최소인 간선부터 mst에 추가해나가며 완성하는 알고리즘) 알고리즘을  통해서 mst를 구했다!

#include<iostream>
#include<queue>
#include<vector>
#include<math.h>
using namespace std;
int ma[101][101];

int visit[101][101];

int xe[4] = { 1,0,-1,0 };
int ye[4] = { 0,1,0,-1 };

int n, m;

vector<pair<int, int>> vec[101];

const int inf = 987654321;
int parent[101];






int find(int v) {//disjoint set find
	if (v == parent[v]) {
		return v;
	}
	else
		return parent[v] = find(parent[v]);
}

void join(int a, int b) {//distjoint set union
	a = find(a);
	b = find(b);
	parent[a] = b;
}



//u번 섬에서 v번 섬으로 가는 직선 최단 거리를 구한다.
int distance(int u, int v) {
	queue < pair<int, int>> q;

	//u번 섬에 있는 칸들을 모두 큐에 넣는다.
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (visit[i][j] == u) {
				q.push({ i, j });
			}
		}
	}

	int mindist = inf;
	int x, y;
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
	
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + xe[k];
			int ny = y + ye[k];
			int dist = 0;

			//한방향으로 계속 이동
			while (true) {
				
				//맵 밖 범위를 넘어간 경우
				if (ma[nx][ny]==-1) break;
				//같은 섬일시 생략.
				if (visit[nx][ny] == u) break;
				if (visit[nx][ny] == v) {
					//도착섬에 도착, 탐색 종료.
					if (dist > 1 && mindist > dist) mindist = dist;
					break;
				}
				else if (visit[nx][ny] == 0) {
					//바다인 경우 거리증가하고 이동
					// 이로인하여, 내륙에서 시작하는 점들을 거를 수 있다. 
					dist++;
					nx += xe[k];
					ny += ye[k];
				}
				else {
					//다른 섬인 경우 더 탐색하지 않는다.
					break;
				}

			}
		}
	}

	//최소거리가 초기값이 아니라면 벡터에 최소거리와 섬의 번호를 넣는다.
	return mindist;
	
}




void bfs(int i, int j, int num) {//i,j에서 시작된 섬에 num의 번호를 붙여 visit에 저장하는 함수.
	visit[i][j] = num;
	vec[num].push_back({ i,j });
	queue<pair<int, int>> qu;
	qu.push({ i,j });
	while (!qu.empty()) {

		int n_i = qu.front().first;
		int n_j = qu.front().second;
		qu.pop();
		for (int k = 0; k < 4; k++) {
			int nxt_i = n_i + xe[k];
			int nxt_j = n_j + ye[k];
			if (ma[nxt_i][nxt_j] == 1 && !visit[nxt_i][nxt_j]) {//다음위치(붙어있는 위치)가 땅이고, 
				visit[nxt_i][nxt_j] = num;						//방문하지 않았다면, 같은섬으로 표기해줘야한다.
				vec[num].push_back({ nxt_i,nxt_j });
				qu.push({ nxt_i,nxt_j });
			}
		}
	}

}

int main() {
	
	cin >> n >> m;





	for (int i = 0; i <= n + 1; i++) {
		for (int j = 0; j <= m + 1; j++) {// 맵을 저장한 ma 함수의 기본 값을 -1로 설정.
			ma[i][j] = -1;
		}
	}


	for (int i = 1; i <= n; i++) {   //입력을 받을때    x,y좌표(혹은 배열 인덱스) 를 한칸씩 +1해준다.
		for (int j = 1; j <= m; j++) {
			cin >> ma[i][j];
		}
	}

	//   -1 -1 -1 -1    위의 두 이중포문으로 배열내부는 이런식으로 생성될 것이다.
	//   -1  0  1  0	ma[i][j] == -1 이라면, 맵밖으로 나간것으로 쉽게 알 수 있다.
	//	 -1  0  1  1
	//   -1  0  0  0    





	int cnt = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!visit[i][j] && ma[i][j] == 1)//visit에 각섬을 번호로 표시.
				bfs(i, j, cnt++);

		}
	}
	for (int i = 1; i <= cnt; i++) {

		parent[i] = i;
	}



	priority_queue<pair<int, pair<int, int>>> pq;


	

	//아래의 2중포문은 "1~cnt 섬 까지의 섬들중 임의의 2섬을 각각 i,j에 담는다! (확통 때 배우는 "조합" 혹은 "콤비네이션" 과 유사

	for (int i = 1; i <= cnt; i++) {//임의 의 두 섬 콤비네이션으로 뽑기. 첫째   

		for (int j = i + 1; j <= cnt; j++) {//둘째.

			int res = distance(i, j);//i>j로 가는 최단거리를 찾아준다.
	
			if (res != inf) {
				pq.push({ -res, { i,j } });//  priority queue는 큰수가 top으로 온다, 
				//따라서 최단거리가 top에 오게 하기 위하여, 거리에 - 를 붙인뒤, 마지막에 *-1 해주자.
				
			}
		}

	}
	



	int ans = 0;
	int t = 0;
	while (!pq.empty()) {
		auto now = pq.top();//가장 적은 가중치의 간선이 먼저 나온다.
		
		pq.pop();
		if (find(now.second.first) != find(now.second.second)) {//같은 그룹이 아니라면
			join(now.second.first, now.second.second);//mst에 합쳐준다.
			t++;//합쳐진 횟수 저장.

			ans += now.first;//해당 간선의 가중치 누적

		}

	}
	ans *= (-1);
	

	//cnt에 현재 들어있는 값은 섬의 개수 +1다.   t는 간선의 개수를 저장해줌.
	//mst의 간선개수 = 정점-1개 여야한다.  따라서 (cnt-1)=정점개수 에 -1 을 해서 cnt-2.

	if (t==cnt-2)
		cout << ans;
	else//mst 완성실패.
		cout << -1;






}

+


풀고 나서 아쉬웠던 부분이 있었는데, 섬간의 거리를 구할때, 섬의 각점마다 bfs를 돌게 짠 부분이 조금 별로였다...
시간초과는 나지 않았지만, 아래의 그림처럼 각 섬의 테두리부터 시작해 bfs를 통해 섬을 확장시켜 나가면서 가장 먼저 서로 만나는 섬들의 거리를 더해 각 섬들간의 최단거리를 찾았다면, 좀더 좋았을 것 같다!

출처: velog.io