2146번: 다리 만들기 (BOJ C/C++)

2146번: 다리 만들기

사용 언어: C++

 

문제

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

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

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

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

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

입력

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

출력

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

 

풀이 1.1

간단하게 생각해보면 그냥 모든 섬의 칸에 대해 BFS를 돌려서 최단 거리를 구할 수 있다.
-> (육지 칸 수) n^2 * (BFS) n^2 = 시간복잡도 O(n^4)이므로 그렇게 바람직한 풀이는 아니다.

/*
푸는 방법 1.1번
-------------
각 섬 숫자 매긴 후 각 섬의 모든 칸에 BFS를 돌려 최단 길이 찾기
-> 육지 칸 수 n^2 * BFS 1번 n^2 = 시간복잡도 O(n^4)
*/

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define MAX 102
int board[MAX][MAX];
int dist[MAX][MAX];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int n;
int vis[MAX][MAX];
vector<int> ans;

bool OOB(int a, int b){
	return a<0 || a>=n || b<0 || b>=n;
}

void island(){
	int cnt=1; //cnt: 섬 번호
	queue<pair<int,int>> Q;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(vis[i][j] || board[i][j]==0) continue;
			vis[i][j]=1;
			board[i][j]=cnt;
			Q.push({i,j});
			while(!Q.empty()){
				auto cur = Q.front(); Q.pop();
				for(int dir=0; dir<4; dir++){
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if(OOB(nx,ny) || vis[nx][ny] || board[nx][ny]==0) continue;
					board[nx][ny] = cnt;
					vis[nx][ny]=1;
					Q.push({nx,ny});
				}
			}
			cnt++;
		}
	}
}

int min_bridge(int x, int y){
	for(int i=0; i<n; i++) fill(dist[i],dist[i]+n,-1);
	queue<pair<int,int>> Q;
	Q.push({x,y});
	dist[x][y]=0;
	while(!Q.empty()){
		auto cur = Q.front(); Q.pop();
		for(int dir=0; dir<4; dir++){
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if(OOB(nx,ny) || dist[nx][ny]>=0) continue; //범위 X, 이미 방문
			if(board[nx][ny] == board[x][y]) continue; //같은 섬
			if(board[nx][ny]!=0 && board[x][y] != board[nx][ny]){ //바다가 아니면 다른 섬
				return dist[cur.X][cur.Y];
			}
			dist[nx][ny] = dist[cur.X][cur.Y]+1;
			Q.push({nx,ny});
		}
	}
	return 99999; //다른 섬 못 만나면 큰 값 반환
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			cin>>board[i][j];
	island();
	
	for(int i=0; i<n; i++) fill(dist[i],dist[i]+n,-1);
	int ans = 999999;
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(board[i][j] != 0)
				ans = min(ans, min_bridge(i,j));
		}
	}
	cout << ans << '\n';
	
	return 0;
}

 

풀이 1.2

풀이 2는 풀이 1을 조금  개선한 풀이다.

푸는 방법 1.2번
-------------
1.1번을 조금 개선해서 최적화한다.
같은 섬에 속한 칸은 동시에 BFS를 돌린다. -> 큐에 전부 넣고 BFS 돌리기
+ 만약 dist 배열을 설정해서 매번 길이를 구할때 dist을 초기화 했다면 
dist 배열을 쓰기보다 vis 배열에 매번 +1 식으로 다른 값으로 매번 하면
vis 배열을 초기화할 필요가 없다.
자세한 풀이는 밑의 링크
https://www.acmicpc.net/source/share/f69dc26b14f24aa688292be57697e7e2

 

풀이 2

모든 섬을 큐에 넣고 한 번에 BFS를 돌려 각 섬이 확장하다가 부딪히는 순간의 거리가 답이다. BFS를 두 번만 사용하므로 시간복잡도가 O(n^2)으로 가장 이상적이다.

/*
푸는 방법 2번
-----------
각 섬 숫자 매긴 후 모든 섬을 큐에 넣고 BFS 동시에 돌려서 각 섬이 확장하다가
다른 섬에 부딪히는 순간을 찾아 최단 거리를 찾으면 된다.
*/

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define MAX 102
int board[MAX][MAX];
int vis[MAX][MAX];
int dist[MAX][MAX];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int n;

bool OOB(int a, int b){
	return a<0 || a>=n || b<0 || b>=n;
}

void island(){
	int cnt=1; //섬 번호
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(vis[i][j] || board[i][j]==0) continue;
			queue<pair<int,int>> Q;
			Q.push({i,j});
			vis[i][j]=1;
			while(!Q.empty()){
				auto cur = Q.front(); Q.pop();
				board[cur.X][cur.Y] = cnt;
				for(int dir=0; dir<4; dir++){
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if(OOB(nx,ny) || vis[nx][ny] || board[nx][ny]==0) continue;
					vis[nx][ny]=1;
					Q.push({nx,ny});
				}
			}
			cnt++;
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			cin>>board[i][j];
	island();
	queue<pair<int,int>> Q;
	for(int i=0; i<n; i++)
		fill(dist[i],dist[i]+n,-1);
	
	//큐에 다 집어넣기
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(board[i][j] != 0){
				dist[i][j] = 0;
				Q.push({i,j});
			}
		}
	}
	int ans = 999999;
	while(!Q.empty()){
		auto cur = Q.front(); Q.pop();
		for(int dir=0; dir<4; dir++){
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if(OOB(nx,ny) || board[nx][ny] == board[cur.X][cur.Y]) continue;
			if(board[nx][ny] != 0)
				ans =  min(ans, dist[nx][ny] + dist[cur.X][cur.Y]);
			else{
				board[nx][ny] = board[cur.X][cur.Y];
				dist[nx][ny] = dist[cur.X][cur.Y] + 1;
				Q.push({nx,ny});
			}
		}
	}
	
	cout << ans << '\n';
	
	return 0;
}