알고리즘 :: 백준 :: DFS, BFS :: 2146 :: 다리 만들기

문제

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

문제접근

• 두 가지 접근으로 문제를 해결할 수 있다.
  1. 각 섬에서 다른 섬 까지의 모든 거리를 계산하고 최단거리를 구한다.
     • 직관적이고 좋은 방법이지만, 모든 점에서부터 BFS를 수행해야 하므로 너무 시간이 오래걸린다는 것이 흠이다.
  2. 각 섬을 한 칸씩 확장해서 서로 다른 인접한 섬과 만날 떄의 거리를 구한다.
     • BFS를 각 섬마다 1회씩만 수행해주면 되므로 속도가 매우 빠르다.
• 2번 방법을 사용해서 문제를 풀어보자.
• 세 가지 배열을 사용해보자.
  1. 문제의 입력을 받을map 배열
  2. 각 섬의 그룹 정보가 담긴 group 배열
  3. 각 섬으로부터의 확장 거리가 담긴 dist 배열
• 먼저, 주어진 입력으로부터 각 섬을 나타내는 1들을 그룹화 하기 위해서는 DFS를 사용하는 방법이 있다.
  • 부분 그래프 개수 구하기 문제 유형을 많이 경험해보았다.
  • 경험해 보지 않았다면 부디 문제를 찾아서 풀어보길 바란다.
• 둘째로, 각 섬의 모든 점을 queue에 넣고 상하좌우 한 칸씩 확장시킨다.
  이때 섬 내부의 점은 거리가 0이고, 확장할 떄마다 1씩 증가한다.
  
• 이런식으로 확장해갈 때, 인접한 섬과 만나는 경우 거리를 계산해주면 된다.
• 확장은 BFS를 사용하며, 방문하는 점마다 확장해주고 다시 push해주면 된다.

코드

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

static int N, map[100][100], group[100][100], dist[100][100];
static constexpr int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

inline bool isPossible(int y, int x) {
	return (0 <= y && y < N) && (0 <= x && x < N);
}

void dfs(int y, int x, int g) {
	group[y][x] = g;
	for (int i = 0; i < 4; ++i) {
		int ny = y + d[i][0], nx = x + d[i][1];
		if (isPossible(ny, nx) && map[ny][nx] && group[ny][nx] != g) dfs(ny, nx, g);
	}
}

void makeGroup() {
	int g = 0;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < N; ++x)
			if (map[y][x] && group[y][x] == 0) 
				dfs(y, x, ++g);
}

void makeBridge() {
	queue<pair<int, int>> q;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < N; ++x) {
			dist[y][x] = -1;
			if (map[y][x]) {
				q.push({y, x});
				dist[y][x] = 0;
			}
		}
	while (!q.empty()) {
		int y = q.front().first, x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = y + d[i][0], nx = x + d[i][1];
			if (isPossible(ny, nx) && dist[ny][nx] == -1) {
				dist[ny][nx] = dist[y][x] + 1;
				group[ny][nx] = group[y][x];
				q.push({ny, nx});
			}
		}
	}
}

int getAnswer() {
	int ret = -1;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < N; ++x)
			for (int i = 0; i < 4; ++i) {
				int ny = y + d[i][0], nx = x + d[i][1];
				if (isPossible(ny, nx) && group[y][x] != group[ny][nx]) {
					if (ret == -1) ret = dist[y][x] + dist[ny][nx];
					else ret = min(ret, dist[y][x] + dist[ny][nx]);
				}
			}
	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < N; ++x)
			cin >> map[y][x];
	
	makeGroup();
	makeBridge();
	cout << getAnswer() << '\n';
}

결과