[C++] 백준 2146번: 다리 만들기

문제 링크

2146번: 다리 만들기

문제 요약

지도 상에 여러 섬들이 존재한다. 이 섬들 중 두 섬을 다리로 연결할 것이다. 이때, 다리 길이를 최소화해야 한다.

접근 방법

DFS 또는 BFS로 모든 섬에 번호를 부여합니다. 방문하지 않은 육지인 점부터 방문 가능한 모든 점들에 같은 번호를 부여하면 됩니다. 그 다음에는 육지인 모든 부분에서 BFS를 돌려서 다른 섬에 도달하기까지 거리를 계산하고, 그 최솟값을 출력해주며 됩니다.

솔직히 골드3 치고는 매우 간단한 문제였습니다.

DFS가 코드가 더 짧게 나와서 번호를 매길 때는 DFS를 사용했습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Data {
	int r, c, cnt;
};

int n, m[101][101], dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
bool visited[101][101];

void dfs(int r, int c, int val)
{
	visited[r][c] = true;
	m[r][c] = val;

	for (int i = 0; i < 4; i++)
	{
		int nr = r + dir[i][0], nc = c + dir[i][1];
		if (nr >= 1 && nr <= n && nc >= 1 && nc <= n && !visited[nr][nc] && m[nr][nc] == -1)
			dfs(nr, nc, val);
	}
}

int bfs(pair<int, int> s, int from)
{
	memset(visited, false, sizeof(visited));

	queue<Data> q;
	q.push({ s.first, s.second, 0 });
	visited[s.first][s.second] = true;

	while (!q.empty())
	{
		Data now = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nr = now.r + dir[i][0], nc = now.c + dir[i][1];
			if (nr < 1 || nr > n || nc < 1 || nc > n || visited[nr][nc])
				continue;
			if (!m[nr][nc])
			{
				visited[nr][nc] = true;
				q.push({ nr, nc, now.cnt + 1 });
			}
			else if (m[nr][nc] != from)
				return now.cnt;
		}
	}

	return -1;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> m[i][j];
			if (m[i][j])
				m[i][j] = -1;
		}
	}

	int idx = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (!visited[i][j] && m[i][j] == -1)
				dfs(i, j, idx++);

	int res = INT_MAX;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (m[i][j])
			{
				int ret = bfs({ i, j }, m[i][j]);
				if (ret != -1)
					res = min(res, ret);
			}
		}
	}

	cout << res;
	return 0;
}