[BOJ] 2146 다리 만들기 C++

개요

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

2146번: 다리 만들기

골드급 BFS 문제다.

풀이

우선 각기 다른 섬부터 구해야 한다.
[BOJ] 2667 단지번호붙이기 C++

위 문제를 풀었던 방식으로 DFS를 이용하여 섬을 구별하기 위한 이름(1,2,3...)을 구해서 붙여줬다.

이제 섬 간의 거리는 BFS를 사용하면 된다.

바다를 제외한 모든 위치에서 다른 섬으로 가는 최단 거리를 전부 구하고, 이 중 다시 최단 거리를 추려냈다.

그냥 바다고 섬이고 돌려도 될 줄 알았으나, 시간 초과가 나버려서 같은 섬끼리는 이동할 수 없도록 조건을 걸어주었다.

(x섬에서 x섬으로 이동 시 이미 최단 거리가 아니기 때문)

인접 행렬 기반 BFS : O(V^2)

코드

#include<iostream>
#include<queue>
using namespace std;
constexpr int LIMIT = 102;
constexpr int MAX = 100000;

struct Block{
	int y;
	int x;
	int dis;
};
int dy[] = { 0,0,1,-1 };
int dx[] = { -1,1,0,0 };
int map[LIMIT][LIMIT]{};
int names[LIMIT][LIMIT]{};
int cnt;
int ans = MAX;
int N;

void DFS(int y, int x)
{
	if (!map[y][x] || names[y][x]) return;
	names[y][x] = cnt;
	
	for (int i = 0; i < 4; i++)
		DFS(y + dy[i], x + dx[i]);
}
void BFS(int y, int x)
{
	bool visited[LIMIT][LIMIT]{};
	int sIsland = names[y][x];

	queue<Block> q;
	q.push({ y, x, 0 });

	while (!q.empty())
	{
		int qy = q.front().y;
		int qx = q.front().x;
		int dis = q.front().dis + 1;
		int nIsland = names[qy][qx];
		q.pop();

		//  OutOfBounds 방지
		if (qy < 1 || qx < 1 || qy > N || qx > N) continue;

		// 메모리 초과 방지
		if (visited[qy][qx]) continue;
		visited[qy][qx] = true;
		
		// 시간 초과 방지 (같은 섬간 이동 제한)
		if (nIsland == sIsland && (y != qy && x != qx)) continue;

		// 최단 경로 체크
		if (nIsland && nIsland != sIsland)
		{
			ans = ans > dis ? dis : ans;
			return;
		}

		for (int i = 0; i < 4; i++)
			q.push({ qy + dy[i], qx + dx[i], dis });
	}
}

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

	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> map[i][j];
		}
	}

	// 섬 구하기(DFS)
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (!map[i][j]) continue;
			cnt++;
			DFS(i, j);
		}
	}
	
	// 최단 경로 다리 찾기(BFS)
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (!map[i][j]) continue;
			BFS(i, j);
		}
	}
	ans -= 2;
	cout << ans;
}