BOJ(c++) / 백준 2146 : 다리 만들기

백준 2146 : 다리 만들기

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

2146번: 다리 만들기

 

문제

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

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

 

입력

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

 

출력

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

 

코드

//백준 2146 다리 만들기
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<vector<int>> board;
int nexti[4] = { 1,0,-1,0 }, nextj[4] = { 0,1,0,-1 };
int visited[101][101] = { 0, };
vector<pair<int, int>> island; //하나의 섬

void DFS(int c_i, int c_j) {
	visited[c_i][c_j] = 1; //방문
	island.push_back({ c_i, c_j }); //한 지역 push

	for (int k = 0; k < 4; k++) {
		//다음 위치 = 현재위치 + next
		int n_i = c_i + nexti[k];
		int n_j = c_j + nextj[k];
		if (n_i < 0 || n_j < 0 || n_i >= N || n_j >= N)
			continue;

		if (visited[n_i][n_j] == 0 && board[n_i][n_j] == 1)
			DFS(n_i, n_j);
	}

}

int min_bridge(vector<pair<int, int>>& a, vector<pair<int, int>>& b) {

	int min_length = 100000; 
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < b.size(); j++) {
			//이을 수 있는 다리 길이
			int length = max(a[i].first, b[j].first) - min(a[i].first, b[j].first) 
						+ max(a[i].second, b[j].second) - min(a[i].second, b[j].second) - 1;
			min_length = min(min_length, length); //가장 짧은 다리
		}
	}
	return min_length;
}

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

	//입력
	cin >> N;
	for (int i = 0; i < N; i++) {
		vector<int> temp;
		for (int j = 0; j < N; j++) {
			int num;
			cin >> num;
			temp.push_back(num);
		}
		board.push_back(temp);
	}

	vector<vector<pair<int, int>>> islands;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			island.clear(); //초기화
			if (visited[i][j] == 0 && board[i][j] == 1) {
				DFS(i, j);
				islands.push_back(island);
			}
		}
	}

	int answer = 1000000;
	for (int i = 0; i < islands.size() - 1; i++) {
		for (int j = i + 1; j < islands.size(); j++) {
			answer = min(answer, min_bridge(islands[i], islands[j])); //가장 짧은 거리
		}
	}

	cout << answer << "\n";


	return 0;
}
//걸린 시간 : 40분

 

설명

DFS를 이용하여 섬의 정보를 벡터에 저장하였다. 섬은 정사각형 모양의 지역들이 붙어있는 모양들이고 격자 i, j를 벡터에 저장하였다.

min_bridge 함수를 사용하여 섬과 섬의 가장 짧은 거리를 구할 수 있다. min_bridge 함수는 한 지점에서 다른 한 지점까지의 거리를 모두 구하고 그중에서 가장 짧은 거리를 선택한다.

각 모든 섬끼리의 min_bridge를 구하고 그 중에서도 가장 짧은 다리의 길이를 출력한다.

 

고찰

걸린 시간 : 40분

난이도를 보고 일단 겁부터 났지만 그래도 쉽게 문제를 구현할 수 있었다.

섬을 구하는 것은 어렵지 않았다. 하지만 섬끼리의 가장 짧은 다리를 구할 때 모든 섬의 위치를 비교해서 시간이 오래 걸리지 않을까 했지만 다행히 시간은 76ms로 시간 초과는 나지 않았다.

DFS, BFS에 대해 자신감이 좀 생긴거 같다. 

 

난이도

Gold 3