[BAEKJOON] 2146 다리 만들기 (C++)

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

2146번: 다리 만들기

 

문제

BFS를 두 번 사용하여 해결하는 문제였다.

시간초과가 날까봐 DP나 육지부분의 경계값들만 추출해서 확인하는 방법을 생각해봤지만 좀 복잡해지기도 하고 확신이 안 서서 그냥 BFS를 이용하여 풀었다.

 

풀이

BFS1.

각 섬을 구분하기 위해 사용한다.

최단 거리를 확인하기 위해 육지 부분에서 다른 육지부분이 나올 때까지 BFS를 실행하는데, 이 때 각 섬을 구분할 필요가 있다.

BFS로 한 육지인 부분만 확장하며 탐색하고 Map 배열에 tmp값을 기록한다.

BFS를 1번 실행했다면 tmp변수를 업데이트 하고 다시 실행한다.

이렇게 하면 Map에 기록된 숫자를 통해 각 섬을 구분할 수 있다.

ex)

5

1 1 0 0 0

1 0 0 0 0

0 2 2 2 0

0 0 0 0 0

0 0 0 0 3

 

BFS2.

최단거리를 구하기 위해 사용한다.

BFS의 확장 조건으로 2가지를 준다.

1. 바다인 경우 확장

2. 시작지점 육지가 아닌 다른 육지인 경우 최단거리를 기록하고 종료

 

BFS의 가장 기본적인 성질은 최단거리를 구하는 것이다. 만약 BFS실행 과정에서 다른 섬이 나왔다면, 해당 위치까지의 거리가 최단거리임을 보장한다. 따라서 더 확인할 필요가 없다.

 

섬의 경계값을 따로 추출할 필요가 없는 게 어차피 경계인지 확인하려면 해당위치에서 4방향(상, 하, 좌, 우)를 확인해야한다.

BFS과정에서 섬의 중앙 육지인 경우도 4방향을 확인한 후에 더이상 BFS를 진행하지 않기 때문에 시간 소요는 동일하다.

(자기 섬인 경우는 BFS확장을 하지 않기 때문)

 

코드

#include <bits/stdc++.h>

#define endl "\n"

using namespace std;

int N, tmp, ans;
int Map[111][111];
int Visited1[111][111];
int Visited2[111][111];

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> Map[i][j];
		}
	}
}

void Bfs1(int y, int x) {
	int xx, yy;
	queue<pair<int, int>> Q;
	Q.push({ y,x }); Visited1[y][x] = 1;
	
	while (!Q.empty()) {
		y = Q.front().first; x = Q.front().second; Q.pop();
		Map[y][x] = tmp;
		for (int i = 0; i < 4; i++) {
			yy = y + dy[i]; xx = x + dx[i];
			if (yy < 1 || xx < 1 || yy > N || xx > N) continue;
			if (Visited1[yy][xx] == true || Map[yy][xx] == 0) continue;
			Visited1[yy][xx] = true; 
			Q.push({ yy, xx });
		}
	}
}

void Bfs2(int y, int x, int k) {
	int xx, yy, cnt; 
	queue<pair<pair<int, int>,int>> Q;
	memset(Visited2, 0, sizeof Visited2);
	Q.push({ {y,x},0}); Visited2[y][x] = 1;

	while (!Q.empty()) {
		y = Q.front().first.first; x = Q.front().first.second; cnt = Q.front().second; Q.pop();
		for (int i = 0; i < 4; i++) {
			yy = y + dy[i]; xx = x + dx[i];
			if (yy < 1 || xx < 1 || yy > N || xx > N) continue;
			if (Visited2[yy][xx] == true || Map[yy][xx] == k) continue;
			Visited2[yy][xx] = true;
			if (Map[yy][xx] != 0) {
				ans = min(ans, cnt); 
				return;
			}
			Q.push({ { yy, xx } , cnt+1});
		}
	}
}
void Solve() {
	tmp = 1; ans = 10000000;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (Map[i][j] == 1 && Visited1[i][j] == 0) { Bfs1(i, j);  tmp++; }
		}
	}



	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (Map[i][j] != 0) Bfs2(i,j,Map[i][j]);
		}	
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << Map[i][j] << " ";
		}
		cout << endl;
	}
	cout << ans;
}	

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	//freopen("input.txt", "r", stdin);
	Input();
	Solve();
	return 0;
}