[백준] 알고리즘 2146번 - 다리 만들기 문제

 

다리 만들기 문제

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

2146번: 다리 만들기

소스코드

#include <bits/stdc++.h>
using namespace std;
int arr[101][101];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
bool check[101][101];
int bridge[101][101];
queue<pair<int, int>> qu;
queue<pair<int, int>> qu1;
int n;

void color_bfs(int x,int y,int color) {
	qu.push({ x,y });
	while (!qu.empty()) {
		int ox = qu.front().first;
		int oy = qu.front().second;
		qu.pop();
		for (int i = 0; i < 4; i++) {
			int nx = ox + dx[i];
			int ny = oy + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (check[nx][ny]==false&&arr[nx][ny]==1) {
				check[nx][ny] = true;
				qu.push({ nx,ny });
				arr[nx][ny] = color;
			}
			if (check[nx][ny]==false&&arr[nx][ny] == 0) { // 섬 밖에 있는 시발롬 색칠해주기 
				check[nx][ny] = true;
				bridge[nx][ny] = 1;
				arr[nx][ny] = color;
				qu1.push({ nx,ny });
			}
		}
	}
}
void bridge_bfs() {
	while (!qu1.empty()) {
		int ox = qu1.front().first;
		int oy = qu1.front().second;
		qu1.pop();
		for (int i = 0; i < 4; i++) {
			int nx = ox + dx[i];
			int ny = oy + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (check[nx][ny] == false && arr[nx][ny] == 0) {
				check[nx][ny] = true;
				arr[nx][ny] = arr[ox][oy];
				qu1.push({ nx,ny });
				bridge[nx][ny] = bridge[ox][oy] + 1;
			}

		}
	}
}
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
   cin >> n;
   for (int i = 0; i < n; i++) {
	   for (int j = 0; j < n; j++) {
		   cin >> arr[i][j];
	   }
   }
   int color = 1;
   for (int i = 0; i < n; i++) {
	   for (int j = 0; j < n; j++) {
		   if (arr[i][j] == 1&&check[i][j]==false) {
			   arr[i][j] = color;
			   color_bfs(i, j, color);
			   color++;
		   }
	   }
   }
   bridge_bfs();
 
   int ans = INT32_MAX;
   for (int i = 0; i < n; i++) {
	   for (int j = 0; j < n; j++) {
		   for (int k = 0; k < 4; k++) {
			   int nx = i + dx[k];
			   int ny = j + dy[k];
			   if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			   if (arr[i][j] != arr[nx][ny]) {
				   ans = min(ans, bridge[i][j] + bridge[nx][ny]);
				    
			   }
		   }
	   }
   } 
   cout << ans;
}

해결방법

이 문제는 저가 dfs, bfs 하면서 가장 어렵게 느껴졌던 문제입니다.

우선 가장 큰 틀은 각각의 섬들에게 넘버를 부여해주는 것입니다.

예를들어 한 뭉치의 섬이 있다면 그 섬들을 1번으로 부여해주고, 다른 뭉치의 섬은 2로 부여해주고, 섬주위의 바로 옆 바다부분을 큐에 넣어주는 작업을 해줘야 합니다.

즉 bfs를 한번 이런 식으로 거친다음

각 섬에서 다리를 연결해주기 위한 길이를 계산하기 위해 부모의 가중치 +1= 현재 방문한 정점을 이용하여 다리의 길이를 셋팅해줍니다. 즉 이것 또한 bfs를 한번더 사용합니다.

마지막으로 각각의 다리 가중치가 다르면 다리를 연결할 수 있으니, 그 가중치에서 가장 작은 값을 출력해주는게 이문제의 정답입니다.