BOJ 2146 : 다리 만들기

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

 

---

[BOJ 2146(G3) 리뷰]

지도에 여러섬이 존재한다. 각 섬에서 다른섬으로 가는 최단경로를 찾아야 한다.

나는 다음과 같이 풀었다.

1.인접한 영역이 같은 섬이므로 1차적으로 BFS를 수행해 각 섬마다 index를 부여했다.

2.(1,1)부터 (n,n)까지 모든 경우에 대해서 현재의 섬index에서 다른 섬의index까지 도달하는데 걸리는 거리의 최소값을 구했다.

 

모든 경우의 수에서 탐색을 진행하다보니 시간복잡도는 엄청나게 증가했다.

처음엔 각각의 위치에 대해서 모든위치에 대해 탐색을 수행했기때문에 1132ms라는 결과가 나왔다.

성공은 했지만 효율적이진 않았다. 그래서 현재 위치와 같은섬에 대해서는 방문을 하지 않도록 코드를 수정했더니 44ms로 엄청나게 빨라졌다.

---

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
using namespace std;

#define X first
#define Y second
int board[102][102];
int dist[102][102];
bool vis[102][102];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> board[i][j];
		}
	}

	//첫번째 작업. 각 나라별 번호 매기기
	int NationIndex=1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (vis[i][j]!=0 || board[i][j] != 1) continue;
			queue <pair<int, int>> Q;
			vis[i][j] = 1;
			Q.push({ i,j });
			while (!Q.empty())
			{
				auto cur = Q.front();
				Q.pop();
				board[cur.X][cur.Y] = NationIndex;
				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 (vis[nx][ny] != 0 || board[nx][ny] != 1) continue;
					vis[nx][ny] = 1;
					Q.push({ nx,ny });
				}
			}
			NationIndex++;
		}
	}

	//두번째작업. 각좌표마다 다른 국가까지의 최소값 구하기.
	int ans = 99999;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (board[i][j] == 0) continue;
			int nation = board[i][j];
			queue <pair<int, int>> Q;
			for (int i = 0; i < n; i++)
				fill(dist[i], dist[i] + n, 0);
			dist[i][j] = 1;
			Q.push({ i,j });
			while (!Q.empty())
			{
				auto cur = Q.front();
				if (board[cur.X][cur.Y] != nation && board[cur.X][cur.Y] != 0) //다른 국가 도착
				{
					ans = min(dist[cur.X][cur.Y], ans);
					break;
				}
				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 (dist[nx][ny] > 0 || board[nx][ny]==nation) continue;
					dist[nx][ny] =dist[cur.X][cur.Y]+1;
					Q.push({ nx,ny });
				}
			}


		}
	}

	cout << ans-2;


}