[BOJ] 17472 다리 만들기 2

문제 요약

문제 링크: 백준 17472 - 다리 만들기 2

문제 설명

---

접근 방법

1. 우선 입력배열에서 섬을 인덱스로 구분을 해준다. bfs나 dfs로 O(N)에 처리해줄 수 있다. 

     문제에서 말해준 내용 중 섬은 최대 6개 라는 것이 중요하다.

2. 각각의 섬에서 다른 섬으로 갈 수 있는 다리의 모든 경우의 수를 vector에 tuple<int, int,int> (가중치, 출발 섬 인덱스, 도착 섬 인덱스) 로 담는다. 코드에서 확인해보면 출발 섬과 도착 섬이 중복된 경우가 하나 씩 생길텐데, 섬의 최대 개수가 많지 않아서 중요하지 않았다. 

3. 이후 가중치 기준으로 오름차순 정렬을 해준 후, 크루스칼 알고리즘을 활용하여 섬들 간의 최소 스패닝 트리를 구성해주면 최단 다리 길이를 구할 수 있다. 

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, mat[101][101], idx = 1;
int vis[101][101], d[4][2] = { {1,0},{-1,0},{0,-1},{0,1} };
int par[7];
vector<tuple<int, int, int>>v;

int get_par(int x) {
	if (x == par[x])
		return x;
	else
		return par[x] = get_par(par[x]);
}

void set_union(int a, int b) {
	a = get_par(a);
	b = get_par(b);
	if (a != b)
		par[b] = a;
}

void bfs(int y, int x) {
	queue<pair<int, int>>q;
	vis[y][x] = idx;
	q.push({ y,x });
	while (q.size()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int yy = y + d[i][0];
			int xx = x + d[i][1];
			if (yy >= n || yy < 0 || xx >= m || xx < 0)
				continue;
			if (vis[yy][xx])
				continue;
			if (mat[yy][xx] == 1) {
				vis[yy][xx] = idx;
				q.push({ yy,xx });
			}
		}
	}
	idx++;
}

void connect(int y, int x) {
	for (int i = 0; i < 4; i++) {
		int ty = y;
		int tx = x;
		int go = 0;
		while (1) {
			int yy = ty + d[i][0];
			int xx = tx + d[i][1];
			if (vis[yy][xx] == vis[y][x])
				break;
			if (yy >= n || yy < 0 || xx >= m || xx < 0)
				break;
			if (vis[yy][xx] != 0) {
				if (go > 1)
					v.push_back({ go, vis[y][x], vis[yy][xx] });
				break;
			}
			go++;
			ty = yy;
			tx = xx;
		}
	}
}

void solve() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (mat[i][j] == 1 && !vis[i][j])
				bfs(i, j);  // 섬 인덱스로 분류
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (mat[i][j] > 0)
				connect(i, j);  // 하나의 섬에서 다른 섬으로 다리가 이어지는 경우 체크
		}
	}
    
    // 섬들을 최소 스패닝 트리로 연결, 따라서 가중치 기준으로 오름차순 정렬 후 크루스칼 알고리즘 활용
	for (int i = 0; i < 7; i++) par[i] = i;
	sort(v.begin(), v.end());
	int ans = 0, con = 0;
	for (int i = 0; i < v.size(); i++) {
		if (get_par(get<1>(v[i])) != get_par(get<2>(v[i]))) {
			set_union(get<1>(v[i]), get<2>(v[i]));
			con++;
			ans += get<0>(v[i]);
		}
		if (con == idx - 2)
			break;
	}
	if (con == idx - 2)
		cout << ans;
	else
		cout << -1;
}

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	input();
	solve();
}

---

마무리

• 최소 스패닝 트리(MST)