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

---

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

---

문제

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

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

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

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

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

---

입력

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

---

출력

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

---

내 풀이

BFS로 섬을 한번씩 돌며 번호를 매기고,

BFS로 섬에서 다른 섬까지 최단 거리를 잰다.

---

코드

#include <iostream>
#include <queue>
#define len 101
#define big 100000

using namespace std;

int N, number, minimum = big;
int map[len][len], island[len][len], dist[len][len];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
queue<int> que_y, que_x;

int length() {
	for (int n = 1; n <= number; n++) {
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				dist[y][x] = big;
				if (island[y][x] == n) {
					que_y.push(y);	que_x.push(x);
					dist[y][x] = 0;
				}
			}
		}

		int y, x, new_y, new_x;
		while (que_y.size() != 0) {
			y = que_y.front();	que_y.pop();
			x = que_x.front();	que_x.pop();

			for (int t = 0; t < 4; t++) {
				new_y = y + dy[t];	new_x = x + dx[t];

				if ((new_y > -1) && (new_y < N) && (new_x > -1) && (new_x < N) && (dist[new_y][new_x] > dist[y][x] + 1)) {
					if (map[new_y][new_x] == 0) {
						que_y.push(new_y);	que_x.push(new_x);
						dist[new_y][new_x] = dist[y][x] + 1;
					}
					else if (island[new_y][new_x] == n) {
						que_y.push(new_y);	que_x.push(new_x);
					}
					else if (island[new_y][new_x] != n) {
						dist[new_y][new_x] = dist[y][x] + 1;
					}
				}
			}
		}

		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if ((map[y][x] == 1) && (island[y][x] != n))
					minimum = (minimum < dist[y][x]) ? minimum : dist[y][x];
			}
		}

	}

	return 0;
}

int BFS(int h, int w) {
	que_y.push(h);	que_x.push(w);

	int y, x, new_y, new_x;
	while (que_y.size() != 0) {
		y = que_y.front();	que_y.pop();
		x = que_x.front();	que_x.pop();

		for (int t = 0; t < 4; t++) {
			new_y = y + dy[t];	new_x = x + dx[t];

			if ((new_y > -1) && (new_y < N) && (new_x > -1) && (new_x < N) && (map[new_y][new_x] == 1) && (island[new_y][new_x] == 0)) {
				que_y.push(new_y);	que_x.push(new_x);
				island[new_y][new_x] = number;
			}
		}
	}

	return 0;
}

int main() {
	scanf("%d", &N);

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			scanf("%1d", &map[y][x]);
		}
	}

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if ((map[y][x] == 1) && (island[y][x] == 0)) {
				number++;
				island[y][x] = number;
				BFS(y, x);
			}
		}
	}

	length();

	printf("%d", minimum - 1);

	return 0;
}