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

문제

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

골드3 BFS 문제이다. 많은 BFS문제를 풀어봤지만 이 문제를 통해 시행착오를 겪으며 BFS 작동방식에 대해 확실하게 알아야겠다고 느꼈다.

풀이

같은 섬 -> 같은 섬으로의 다리가 만들어 질 수 있기 때문에 보드에 입력을 받을때 육지에 대해서는 1을 -1로 치환하여 받아준다. 이후 setNumber를 통해 같은 섬마다 같은 번호를 붙이도록 BFS를 돌려주었다.

번호를 매겼으면 이제 다리를 만들어주기위해 각 섬마다 BFS를 돌려주는데 BFS를 진행하다 바다(보드의 0)를 만나면 Queue에 넣어주면서 다리를 계속 연결할 수 있도록 하였고, BFS를 진행하다 다른 번호를 가진 섬을 만나게 되면 다리가 연결된 것이므로 탐색을 종료하고 다리의 길이를 return해주었다.(가장 먼저 다른 섬과 만난 다리의 길이가 최솟값임)

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define x first
#define y second

using namespace std;

int n;
int idx = 0;
int result = 1000;
int board[101][101];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void setNumber()
{
	queue<pair<int, int>> q;
	bool visited[101][101];
	memset(visited, false, sizeof(visited));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (visited[i][j] || board[i][j] == 0)
			{
				continue;
			}

			idx++;
			q.push({ i, j });
			visited[i][j] = true;
			board[i][j] = idx;

			while (!q.empty())
			{
				auto cur = q.front();
				q.pop();

				for (int dir = 0; dir < 4; dir++)
				{
					int nx = cur.x + dx[dir];
					int ny = cur.y + dy[dir];

					if (nx < 0 || nx >= n || ny < 0 || ny >= n)
					{
						continue;
					}
					if (visited[nx][ny] || board[nx][ny] == 0)
					{
						continue;
					}

					q.push({ nx, ny });
					visited[nx][ny] = true;
					board[nx][ny] = idx;
				}
			}
		}
	}
}

int makeBridge(int num)
{
	queue<pair<int, int>> q;
	bool visited[101][101];
	int leng = 0;

	memset(visited, false, sizeof(visited));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (board[i][j] == num)
			{
				visited[i][j] = true;
				q.push({ i,j });
			}
		}
	}

	while (!q.empty())
	{
		int s = q.size();

		for (int i = 0; i < s; i++)
		{
			auto cur = q.front();
			q.pop();

			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];

				if (nx < 0 || nx >= n || ny < 0 || ny >= n)
				{
					continue;
				}

				if (board[nx][ny] == 0 && !visited[nx][ny])
				{
					visited[nx][ny] = true;
					q.push({ nx, ny });
				}
				else if (board[nx][ny] != 0 && board[nx][ny] != num)
				{
					return leng;
				}
			}
		}
		leng++;
	}
}

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

	cin >> n;

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

	setNumber();

	for (int i = 0; i < idx; i++)
	{
		result = min(result, makeBridge(i + 1));
	}

	cout << result;
}