2146번: 다리 만들기

문제 설명

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

2146번: 다리 만들기

[문제]

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

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

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

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

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

 

[입력]

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

 

[출력]

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

 

[예제 입력 1]

10
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

[예제 출력 1]

3

---

풀이

 이 문제를 풀기 위해선 크게 2가지 과정이 필요하다. 첫 번째는 주어진 지도를 가지고 해당 지점이 어느 섬에 속한지 구분하는 것이고, 두 번째는 하나의 섬 위치에서 전체 지도를 돌며 최단 경로(정확히는 최단 경로 - 1 값인 다리 길이)를 탐색하는 것이다.

 예제를 기반으로 설명하자면, 우선 지도를 입력받게 되면 모든 지점 1과 0으로만 구분되어 있기 때문에, 해당 지점이 어느 섬에 속해 있는 지 불명확하여 BFS를 기반으로 한 섬 구분 함수를 통해 해당 섬을 1부터 하나씩 증가하여 구분짓도록 한다. 그렇게 되면 입력받은 섬의 결과가 다음과 같다.

초기 입력

섬 구분 함수 결과

 이를 통해 섬의 구분을 완료하고 나면 섬 간의 최단 경로를 탐색해야 되는데, 이 경우 일일히 섬 1과 2, 1과 3, 2와 3을 지정하여 최단 경로를 얻기 보다는 단순히 반복문을 통해 모든 경우의 수를 탐색하게 했다. 우선적으로 문제에서 얻어야 하는 것이 어느 섬과 연결되어 있냐가 아닌 단순한 값이기 때문에, 어느 섬과 닿았느냐가 중요하진 않다. 그러기 때문에 증가하는 반복문을 통해 특정 섬의 값에서 BFS 기반 탐색 함수를 진행하는 경우, 어느 섬에 도달한 위치의 값이 자신의 값보다 크기만 하면 해당 최단 경로 값을 반환하면 된다. 그러면 현재 섬의 값이 1인 경우 자연스럽게 2, 3인 지점까지의 최단 경로를 탐색하게 되고, 2인 경우 3과의 최단 경로만을 탐색하게 되어 결과적으로 모든 경우의 수를 탐색할 수 있게 된다.

 추가적으로 시간을 줄이기 위해, 최단 경로 탐색 함수 호출 조건과 탐색 중에서의 조건을 추가했다. 우선 탐색 함수 호출 조건으로 섬의 내륙인 경우(상하좌우 위치 값이 모두 자기와 같은 경우) 함수 호출을 못하게 했고, 탐색 중에서의 조건으로는 BFS를 통해 탐색을 넓혀가다 자신이 속한 섬의 일부(자신과 값이 동일한 곳)를 만난 경우 애초에 최단 경로가 아닐꺼라 판단하여 해당 지점 탐색을 멈추게 했다.

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

using namespace std;

vector<vector<int>> map;//지도
int islandType[100][100] = { 0, };//섬 구분 지도
int visited[100][100] = { 0, };

struct infor {//위치 정보 구조체
	int r, c, cost;
};

bool check(int N, int r, int c) {//탐색할 만한 곳인지
	if (0 == r || r == N - 1 || 0 == c || c == N - 1) //지도의 가장자리는 탐색 ok
		return true;
	//상하좌우 모두 육지면 탐색 X
	if (map[r + 1][c] == 1 && map[r - 1][c] == 1 && map[r][c + 1] == 1 && map[r][c - 1] == 1)
		return false;

	return true;
}

void paintIsland(int N, int r, int c, int island) {//BFS 기반 섬 구분
	queue<pair<int, int>> q;
	q.push(make_pair(r, c));

	while (!q.empty()) {
		int hereR, hereC;
		hereR = q.front().first;
		hereC = q.front().second;
		q.pop();

		if (0 > hereR || hereR >= N || 0 > hereC || hereC >= N) //인덱스 밖
			continue;

		if (map[hereR][hereC] == 0 || visited[hereR][hereC] == 1) //바다거나 방문해봤으면
			continue;

		visited[hereR][hereC] = 1;
		islandType[hereR][hereC] = island;

		q.push(make_pair(hereR + 1, hereC));
		q.push(make_pair(hereR - 1, hereC));
		q.push(make_pair(hereR, hereC + 1));
		q.push(make_pair(hereR, hereC - 1));
	}
}

int calDist(int N, int r, int c, int island) {//BFS 기반 최단경로(다리 길이) 탐색
	memset(visited, 0, sizeof(visited));
	queue<infor> q;
	q.push({ r,c,0 });

	while (!q.empty()) {
		infor here = q.front(); q.pop();

		if (0 > here.r || here.r >= N || 0 > here.c || here.c >= N) //인덱스 밖
			continue;

		if (visited[here.r][here.c] == 1) //방문해봤으면
			continue;

		if (islandType[here.r][here.c] > island) //현 위치의 섬이 지금과 다르면
			return here.cost - 1; //다리 길이 반환

		if (here.cost > 0 && islandType[here.r][here.c] == island)//동일한 섬의 지점이면
			continue;

		visited[here.r][here.c] = 1;
		here.cost++;

		--here.r;//상
		q.push(here);
		++here.r; ++here.c;//우
		q.push(here);
		here.c -= 2;//좌
		q.push(here);
		++here.c; ++here.r;//하
		q.push(here);
	}

	return 10000;
}

int main() {
	int N, tmp, island = 0;
	int answer = 10000;
	cin >> N;

	for (int i = 0; i < N; i++) {//맵 초기화
		vector<int> temp;
		for (int j = 0; j < N; j++) {
			cin >> tmp;
			temp.push_back(tmp);
		}
		map.push_back(temp);
	}

	for (int i = 0; i < N; i++) //섬 구분
		for (int j = 0; j < N; j++)
			if (map[i][j] == 1 && islandType[i][j] == 0)
				paintIsland(N, i, j, ++island);

	for (int startIsland = 1; startIsland < island; startIsland++)//최단 다리 길이 탐색
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				if (islandType[i][j] == startIsland && check(N, i, j))
					answer = min(answer, calDist(N, i, j, startIsland));

	cout << answer;

	return 0;
};

---

결과

위에는 함수 호출 조건을 설정한 경우, 아래는 단순히 모든 섬의 지점에서 최단 경로 탐색 함수를 호출한 경우이다.