[백준 2146] 다리 만들기

문제링크 : https://www.acmicpc.net/problem/2146

💻 문제 풀이 : C++

#include <iostream>
#include <queue>
#include <cstring>

#define MAP_SIZE 105

using namespace std;

struct Coord {
	int row;
	int col;
};

int N;
int MAP[MAP_SIZE][MAP_SIZE];
int visited[MAP_SIZE][MAP_SIZE];
int bridge[MAP_SIZE][MAP_SIZE];

int dr[] = { 0, 0, -1, 1 };
int dc[] = { -1, 1, 0, 0 };

int my_min(int a, int b)
{
	return a < b ? a : b;
}

void idx_bfs(Coord start, int idx)
{
	queue<Coord> nowQ;
	nowQ.push(start);
	while (!nowQ.empty())
	{
		Coord now = nowQ.front();
		nowQ.pop();
		for (int i = 0; i < 4; i++)
		{
			Coord next = { now.row + dr[i], now.col + dc[i] };
			if (next.row < 0 || next.col < 0 || next.row >= N || next.col >= N) continue;
			if (MAP[next.row][next.col] == 0) continue;
			if (visited[next.row][next.col] != 0) continue;
			visited[next.row][next.col] = idx;
			nowQ.push(next);
		}
	}
}

int bridge_bfs(Coord start, int idx)
{
	queue<Coord> nowQ;
	nowQ.push(start);
	while (!nowQ.empty())
	{
		Coord now = nowQ.front();
		nowQ.pop();
		for (int i = 0; i < 4; i++)
		{
			Coord next = { now.row + dr[i], now.col + dc[i] };
			if (next.row < 0 || next.col < 0 || next.row >= N || next.col >= N) continue;
			// if (MAP[next.row][next.col] == 0) continue;
			if (visited[next.row][next.col] == idx) continue;
			if (bridge[next.row][next.col] != 0) continue;
			if (visited[next.row][next.col] != 0 && visited[next.row][next.col] != idx) return bridge[now.row][now.col] - 1;
			bridge[next.row][next.col] = bridge[now.row][now.col] + 1;
			nowQ.push(next);
		}
	}
	int debug = 1;
	return 2134567890;
}

int main()
{
	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> MAP[i][j];

	// 섬에 번호 붙이기 BFS
	int idx = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (MAP[i][j] == 1 && visited[i][j] == 0)
			{
				visited[i][j] = idx;
				idx_bfs({ i, j }, idx);
				idx++;
			}
		}
	}

	int debug = 1;
	int answer = 2134567890;
	// 다리만들기 BFS
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (MAP[i][j] == 1)
			{
				memset(bridge, 0, sizeof(bridge));
				bridge[i][j] = 1;
				answer = my_min(answer, bridge_bfs({ i, j }, visited[i][j]));
			}
		}
	}

	cout << answer << endl;

	return 0;
}

---

📌 memo 😊

---

ref)