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

2차원 배열에서 1은 육지이며, 붙어있는 1은 같은 육지입니다.
여러 육지가 있을 때 하나의 다리를 만들어서 육지를 이을 것입니다.
이 때 가장 짧게 만들 수 있는 다리의 길이를 구하는 문제입니다.

1   1   1   0   0   0   0   1   1   1
1   1   1   1   0   0   0   0   1   1
1   0   1   1   0   0   0   0   1   1  
0   0   1   1   1   0   0   0   0   1
0   0   0   1   0   0   0   0   0   1
0   0   0   0   0   0   0   0   0   1
0   0   0   0   0   0   0   0   0   0
0   0   0   0   1   1   0   0   0   0
0   0   0   0   1   1   1   0   0   0
0   0   0   0   0   0   0   0   0   0
(map)
다음과 같이 지역에 대한 map이 있을 때


먼저 영역을 각각 2, 3, 4 .... 과 같이 나누었습니다.
숫자 1을 발견하면 DFS를 통해서 전부 2로 만들고
다음번에 발견하게되면 3으로 만드는 방식으로 진행하였습니다.

2   2   2   0   0   0   0   3   3   3
2   2   2   2   0   0   0   0   3   3
2   0   2   2   0   0   0   0   3   3  
0   0   2   2   2   0   0   0   0   3 
0   0   0   2   0   0   0   0   0   3
0   0   0   0   0   0   0   0   0   3
0   0   0   0   0   0   0   0   0   0
0   0   0   0   4   4   0   0   0   0 
0   0   0   0   4   4   4   0   0   0
0   0   0   0   0   0   0   0   0   0
(map)


0   0   0   $   $   $   $   0   0   0
0   0   0   0   $   $   $   $   0   0
0   $   0   0   $   $   $   $   0   0  
$   $   0   0   0   $   $   $   $   0 
$   $   $   0   $   $   $   $   $   0
$   $   $   $   $   $   $   $   $   0
$   $   $   $   $   $   $   $   $   $
$   $   $   $   0   0   $   $   $   $ 
$   $   $   $   0   0   0   $   $   $
$   $   $   $   $   $   $   $   $   $
(dis)

거리에 대한 2차원 배열도 만들었습니다.
기본 값들로 987654321이라는 큰값을 넣어두었습니다 ($ = 987654321)
땅이 있는곳들은 0으로 지정해 두었습니다.

땅이 있는곳들부터 BFS를 통해서 다른 땅이 나올 때 까지 반복해서
dis 배열에 거리정보를 저장합니다.
그리고 다른 땅이 나오게 되면 현재 거리를 기억하고 가장 짧은 거리를 계속 찾습니다.

모든 위치에 BFS를 사용해주고 가장 짧았던 거리를 출력하여 문제를 풀었습니다.

 

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

using namespace std;

int n;
int map[110][110];
int dis[110][110];
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };

void init()
{
	for (int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j){
			if(map[i][j] == 0){
				dis[i][j] = 987654321;
			}
		}
	}
}

void DFS(int a, int b, int c)
{
	if (map[a][b] == 1) {
		map[a][b] = c;
		dis[a][b] = 0;
		for (int l = 0; l < 4; ++l) {
			int x = moveX[l] + a;
			int y = moveY[l] + b;
			if (x >= 0 && y >= 0 && x < n && y < n) {
				DFS(x, y, c);
			}
		}
	}
}

int BFS(int a, int b, int c)
{
	int count;
	int minDis = 987654321;
	
	queue<int> q1;
	queue<int> q2;
	q1.push(a);
	q2.push(b);
	
	while(!q1.empty()){
		int qX = q1.front();
		int qY = q2.front();
		q1.pop();
		q2.pop();
		
		for(int l = 0; l < 4; ++l){
			int x = moveX[l] + qX;
			int y = moveY[l] + qY;
			
			if(x >= 0 && y >= 0 && x < n && y < n){
				if(map[x][y] > 0 && c != map[x][y]){
					minDis = min(minDis, dis[qX][qY]);
					continue;
				}
				
				if(map[x][y] == 0 && dis[x][y] > dis[qX][qY] + 1){
					dis[x][y] = dis[qX][qY] + 1;
					q1.push(x);
					q2.push(y);
				}
			}
		}
	}
	return minDis;
}
							

int main(int argc, char *argv[])
{
	memset(map, 0, sizeof(map));
	memset(dis, 0, sizeof(dis));
	int count = 2;
	int minN = 987654321;
	
	cin >> n;

	for (int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j){
			cin >> map[i][j];
			dis[i][j] = 987654321;
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (map[i][j] == 1) {
				DFS(i, j, count);
				count++;
			}
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (map[i][j] > 1) {
				init();
				minN = min(minN, BFS(i, j, map[i][j]));
			}
		}
	}

	cout << minN << endl;
	
	return 0;
}