BOJ 2146 - 다리 만들기

문제 링크

---

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

문제 해결

---

1. BFS를 이용해서 각 대륙(0이 아닌 곳)에서 바다(0인 곳)와 인접해있는 곳에 새로운 번호를 부여.

  

2. 각 번호에서 0,1,자기 자신의 번호 이외의 값을 만날 때까지 다시 BFS.

주의할 점

---

BFS를 이용해서 새로운 번호를 부여하는 시간 복잡도는 O(N^2)이지만, 새로 번호를 부여받은 곳에서 다른 대륙까지의 BFS를 이용할 시 O(N^4)까지 올라갈 수 있으므로, N 제한이 작을 때만 사용해야한다. 

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<cstdio>
	#include<cstdlib>
	#include<iostream>
	#include<vector>
	#include<algorithm>
	#include<string.h>
	#include<string>
	#include<functional>
	#include<queue>
	#include<stack>
	#include<cstring>
	#include<cmath>
	#include<climits>
	#include<map>
	#include<set>
	using namespace std;
	int N;
	int mapp[105][105];
	bool visit[105][105];
	int x_move[] = {0,0,-1,1};
	int y_move[] = {-1,1,0,0};
	int ans = 1e6; // 답을 구하는 곳.
	int cnt=2;
	void bfs(int x, int y){
	queue<pair<int, int> > q;
	visit[x][y] = true;
	q.push({x,y});
	bool chk = false;
	while(!q.empty()){
	int rx = q.front().first;
	int ry = q.front().second;
	q.pop();
	for(int i=0;i<4;i++){
	int nx = rx + x_move[i];
	int ny = ry + y_move[i];
	if(nx>0 && nx<=N && ny>0 && ny<=N){
	if(!mapp[nx][ny]&& !chk){
	chk = true;
	}
	if(!visit[nx][ny] && mapp[nx][ny]){
	visit[nx][ny] = true;
	q.push({nx,ny});
	}
	}
	}
	if(chk){
	mapp[rx][ry] = cnt;
	chk = false;
	}
	}
	}
	int find_bridge(int x, int y, int s){
	queue<pair<int, int> > q;
	int temp_ans = 1e6;
	bool temp_visit[105][105];
	int dist[105][105];
	memset(dist,0,sizeof(dist));
	memset(temp_visit,false,sizeof(temp_visit));
	q.push({x,y});
	temp_visit[x][y] = true;
	while(!q.empty()){
	int rx = q.front().first;
	int ry = q.front().second;
	q.pop();
	for(int i=0;i<4;i++){
	int nx = rx +x_move[i];
	int ny = ry +y_move[i];
	if(nx>0 && nx<=N && ny>0 && ny<=N){
	if(mapp[nx][ny] != 1 && mapp[nx][ny]!=0 && mapp[nx][ny]!=s){
	temp_ans = min(dist[rx][ry],temp_ans);
	}
	if(!mapp[nx][ny] && !temp_visit[nx][ny]){
	dist[nx][ny] = dist[rx][ry] + 1;
	q.push({nx,ny});
	}
	temp_visit[nx][ny]=true;
	}
	}
	}
	return temp_ans;
	}
	int main(){
	cin >> N;
	int temp;
	for(int i=1;i<=N;i++){
	for(int j=1;j<=N;j++){
	cin >> mapp[i][j];
	}
	}
	for(int i=1;i<=N;i++){
	for(int j=1;j<=N;j++){
	if(!visit[i][j] && mapp[i][j]){
	bfs(i,j);
	cnt++;
	}
	}
	}
	for(int i=1;i<=N;i++){
	for(int j=1;j<=N;j++){
	if(mapp[i][j]!=0 && mapp[i][j]!=1){
	temp = find_bridge(i,j,mapp[i][j]);
	ans = min(ans,temp);
	}
	}
	}
	printf("%d",ans);
	return 0;
	}

view raw BOJ 2146.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.