[백준 2146] 다리 만들기 (C++)

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

문제

---

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

---

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

 

출력

---

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

 

문제 풀이

---

bfs 문제.

섬을 탐색하여 각 섬에 번호를 부여하여 섬들을 구분 짓는다. 이후 바다이면서 섬에 맞닿아 있는 부분만 bfs를 진행할 큐에 모두 넣어 놓은 후, 몇 번만에 다른 섬에 도달할 수 있는지를 확인한다. 다른 섬인지를 확인해야 하므로 탐색 시 현재 위치, 처음 push할 때의 맞닿은 섬의 번호, 현재까지의 탐색한 루트의 길이를 저장해둔다. 현재 위치가 섬의 가장자리와 맞닿아 있는 바다이고, 해당 섬의 번호가 처음 push할 때의 맞닿은 섬의 번호와 다르다면 다른 섬으로 취급할 수 있다.

 

각 칸을 이미 탐색했는지의 여부는 일반적인 bfs처럼 bool 타입 2차원 배열로 넣으면 섬의 가장자리와 맞닿아 있는 바다를 이미 탐색했기 때문에 답이 나오지 않는다. 따라서 각 칸에 방문했다면 해당 루트의 탐색을 시작하는 섬의 번호를 저장해둔다. 이를 위해 방문 여부를 확인하는 배열은 set<int> 타입의 배열로 선언하였다. 예를 들어 섬이 세 개이고 map[i][j]에 {1, 2}가 저장되어 있다면 첫번째 섬과 두번째 섬으로부터 출발한 루트를 탐색했으며, 세번째 섬으로부터의 출발한 루트는 아직 탐색하지 않았음을 의미한다.

 

아래는 코드.

bfs 탐색은 2번 진행된다. 섬에 번호를 부여하기 위해 isVisited 배열과 bfsQueue를 사용해 -1, -2, -3 .. 등의 번호를 부여하였다. (양수여도 상관없다.)

그 후 지도를 전체 탐색하여 각 섬에 맞닿아 있는 바다들을 전부 큐에 삽입한다. 해당 큐는 위에서 이야기했듯, 다른 섬인지 확인해야 하므로 탐색 시 현재 위치, 처음 push할 때의 맞닿은 섬의 번호, 현재까지의 탐색한 루트의 길이를 저장하는 구조체를 타입으로 가진다.

전부 큐에 삽입하면 다음 움직일 칸이 특정 섬으로부터 시작된 탐색을 이미 진행했는지 확인하면서 bfs 탐색을 진행한다. 가장 첫번째로 시작 섬과 다른 섬과 맞닿아 있는 루트를 찾아낸다면 해당 루트의 길이가 최소가 된다. 

#include <iostream>
#include <queue>
#include <utility>
#include <set>
using namespace std;
int** map;
bool** isVisited;
set<int>** checkVisitedWithNum;
set<int>::iterator it;

int currentIslandCount = 1;
queue<pair<int, int>> bfsQueue;
int N;

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

struct info
{
	int x;
	int y;
	int length;
	int startLand;
	info(int a, int b, int c, int d)
	{
		x = a;
		y = b;
		length = c;
		startLand = d;
	}
};

queue<info> bridgeQueue;

void checkIslands(int x,  int y)
{
	isVisited[x][y] = true;
	map[x][y] = -1 * currentIslandCount;
	bfsQueue.push(pair(x, y));
	while (!bfsQueue.empty())
	{
		pair<int, int> current = bfsQueue.front();
		for (int i = 0; i < 4; i++)
		{
			int nextX = current.first + dx[i];
			int nextY = current.second + dy[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && isVisited[nextX][nextY]==false && map[nextX][nextY]==-1)
			{
				isVisited[nextX][nextY] = true;
				map[nextX][nextY] = -1 * currentIslandCount;
				bfsQueue.push(pair(nextX, nextY));
			}
		}
		bfsQueue.pop();
	}
	currentIslandCount++;
}

bool isTouchToOtherIsland(info currentInfo)
{
	for (int i = 0; i < 4; i++)
	{
		int nextX = currentInfo.x + dx[i];
		int nextY = currentInfo.y + dy[i];
		if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && map[nextX][nextY] < 0 && map[nextX][nextY] !=  currentInfo.startLand)
		{
			return true;
		}
	}
	return false;
}

void checkBridgeLength()
{
	while (!bridgeQueue.empty())
	{
		info current = bridgeQueue.front();
		if (isTouchToOtherIsland(current))
		{
			cout << current.length << "\n";
			break;
		}
		for (int i = 0; i < 4; i++)
		{
			int nextX = current.x + dx[i];
			int nextY = current.y + dy[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && map[nextX][nextY] == 0)
			{
				it = checkVisitedWithNum[nextX][nextY].find(current.startLand);
				if (it == checkVisitedWithNum[nextX][nextY].end())
				{
					checkVisitedWithNum[nextX][nextY].insert(current.startLand);
					bridgeQueue.push(info(nextX, nextY, current.length + 1, current.startLand));
				}
			}
		}
		bridgeQueue.pop();
	}
}

int isEdge(int x, int y)
{
	for (int i = 0; i < 4; i++)
	{
		int nextX = x+ dx[i];
		int nextY = y + dy[i];
		if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N&& map[nextX][nextY] < 0)
		{
			return map[nextX][nextY];
		}
	}
	return 0;
}

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

	cin >> N;
	map = new int*[N];
	isVisited = new bool*[N];
	checkVisitedWithNum = new set<int>*[N];
	for (int i = 0; i < N; i++)
	{
		map[i] = new int[N];
		isVisited[i] = new bool[N];
		checkVisitedWithNum[i] = new set<int>[N];
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
			isVisited[i][j] = false;
			if (map[i][j] == 1)
			{
				map[i][j] = -1;
			}
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (map[i][j] == -1 && isVisited[i][j] == false)
			{
				checkIslands(i, j);
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (isVisited[i][j] == false && isEdge(i, j) != 0)
			{
				int islandNum = isEdge(i, j);
				checkVisitedWithNum[i][j].insert(islandNum);
				bridgeQueue.push(info(i, j, 1, islandNum));
			}
		}
	}
	checkBridgeLength();
	return 0;
}