백준 2146번, 다리 만들기 풀이

문제

백준 2146번

풀이

임의의 섬 하나를 지정합니다.

그리고, 그 섬의 테두리를 계속 한칸씩 늘려줍니다.

길이가 1인 경우 섬의 모습

테스트케이스의 경우, 왼쪽 윗 섬을 잡고, 길이를 1씩 늘리면 위와 같은 모양이 됩니다.

길이가 2인 경우 섬의 모습

계속해서 길이를 2로 늘려주면, 위와 같이 됩니다.

길이가 3인 경우 섬의 모습

마지막으로 길이가 3이 되면, 다른 섬과 닿게 됩니다.

 

 

위 과정은 너비 우선 탐색, BFS로 해결할 수 있습니다.

 

이러한 과정을 나머지 섬에도 모두 해주면서 답을 갱신해주면 됩니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

vector<pii> direct = {
		{1,  0},
		{0,  1},
		{-1, 0},
		{0,  -1}
};

vector<queue<pair<pii, pii>>> q;
int vis[101][101], mp[101][101], island[101][101], n, num = 1;

void dfs(int x, int y) {
	if (!island[x][y]) {
		island[x][y] = num;
		q.back().push({{x, y},
		               {0, num}});
	}

	for (const auto &mv : direct) {
		int xx = x + mv.first, yy = y + mv.second;
		if (xx < 0 || yy < 0 || xx >= n || yy >= n || island[xx][yy]) continue;
		if (mp[xx][yy]) {
			island[xx][yy] = num;
			q.back().push({{xx, yy},
			               {0, num}});
			dfs(xx, yy);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> mp[i][j];

	//DFS를 사용하여 섬에 번호를 부여해줍니다.
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (!island[i][j] && mp[i][j]) q.emplace_back(), dfs(i, j), ++num;
		}

	int ans = 1e9;
	for (int i = 1; i < num; i++) {
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++) vis[j][k] = 0;

		//한칸씩 늘려가면서 정답을 갱신합니다.
		auto &rq = q[i - 1];
		int f = 0;
		while (!rq.empty() && !f) {
			auto xy = rq.front();
			rq.pop();
			for (const auto &mv : direct) {
				int x = xy.first.first + mv.first, y = xy.first.second + mv.second;
				if (x < 0 || x >= n || y < 0 || y >= n) continue;
				if (island[x][y] && island[x][y] != xy.second.second) {
					ans = min(ans, xy.second.first);
					f = 1;
					break;
				}
				if (!vis[x][y]) {
					vis[x][y] = 1;
					rq.push({{x, y}, {xy.second.first + 1, xy.second.second}});
				}
			}
		}
	}

	cout << ans;
}