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

문제

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

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

 

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

 

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

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

 

출력

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

 

풀이

먼저 dfs를 통해 섬에 그룹 번호를 붙여줍니다.

예시 그림의 좌상단에 위치한 섬은 1번 그룹, 우상단에 위치한 섬은 2번 그룹, 하단부에 위치한 섬은 3번 그룹이 됩니다.

 

1번 그룹에 속해있는 2차원 배열 인덱스는 Group[1]에,2번 그룹에 속해있는 2차원 배열 인덱스는 Group[2]에 보관합니다.

 

이중 for문을 통해 그룹간 다리길이를 비교합니다. 이때 장애물이 없는 map에서 최단 경로는 단순 절댓값의 차이가 됩니다. 즉 bfs 필요없이 간단한 수식으로 최단 경로를 구할 수 있습니다.

 

(1번 그룹에 속한 정점 ↔ 2번 그룹에 속한 그룹 정점)

(1번 그룹에 속한 정점 ↔ 3번 그룹에 속한 그룹 정점)

(2번 그룹에 속한 정점 ↔ 3번 그룹에 속한 그룹 정점)

모든 경우를 계산하여 가장 거리가 짧은 값을 답으로 갱신합니다.

 

전체 소스코드는 아래와 같습니다.

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 110;
int map[MAX][MAX];
bool visited[MAX][MAX];
int N;

int answer = 987654321;

int dirX[4] = { -1, 0, 1, 0 };
int dirY[4] = { 0, 1, 0, -1 };

struct myData {
	int x;
	int y;
};

vector<myData> Graph[10100];

bool isInRange(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < N) {
		return true;
	}
	else
		return false;
}

void dfs(int x, int y, int num) { // 단지 번호 붙이기
	map[x][y] = num;
	visited[x][y] = true;

	Graph[num].push_back({ x, y });

	for (int i = 0; i < 4; i++) {
		int nextX = x + dirX[i];
		int nextY = y + dirY[i];

		if (isInRange(nextX, nextY) && visited[nextX][nextY] == false && map[nextX][nextY] != 0) {
			dfs(nextX, nextY, num);
		}
	}
}

int abs(int a, int b) {
	if (a > b) return a - b;
	else return b - a;
}

int main() {
	cin >> N;

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

	int number = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1 && visited[i][j] == false) {
				dfs(i, j, number);
				number++;
			}
		}
	}

	for (int i = 1; i < number; i++) { 
		for (int j = i + 1; j < number; j++) {
			// Group[i]와 Group[j] 비교
			for (int p = 0; p < Graph[i].size(); p++) {
				for (int k = 0; k < Graph[j].size(); k++) {
					int group1x = Graph[i][p].x;
					int group1y = Graph[i][p].y;

					int group2x = Graph[j][k].x;
					int group2y = Graph[j][k].y;

					int length = abs(group1x, group2x) + abs(group1y, group2y) - 1;
					if (answer > length) answer = length;
				}
			}
		}
	}

	cout << answer;

	return 0;
}