[백준 2146] 다리 만들기

# 문제링크

www.acmicpc.net/problem/2146

2146번: 다리 만들기

DFS를 사용하여 섬을 구분하고, BFS를 사용해서 가장 짧은 거리를 찾는 문제. DFS, BFS 둘 다 써야하는 문제였어요. 

 

문제 예시로 준 섬입니다.

이를 아래처럼 0과 1로 표시할 수 있습니다. 

1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

 

DFS 를 활용해 섬을 1부터 차례대로 구분해주었습니다. 1, 2, 3번 섬이 있습니다. 1이 있던 곳에 visited를 1로 채워두었습니다. 또, 향후 BFS를 위해서 1일때 좌표값을 queue에 미리 넣어둡니다. 

 

// map
1 1 1 0 0 0 0 2 2 2
1 1 1 1 0 0 0 0 2 2
1 0 1 1 0 0 0 0 2 2
0 0 1 1 1 0 0 0 0 2
0 0 0 1 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 3 3 0 0 0 0
0 0 0 0 3 3 3 0 0 0
0 0 0 0 0 0 0 0 0 0


// visited
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

 

map의 각 섬에서 BFS를 해줍니다. visited는 visit 할 때마다 이전 값보다 1씩 증가시켜줍니다. 

 

// map
1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 1 2 2 2 2
1 1 1 1 1 1 2 2 2 2
1 1 1 1 1 1 1 2 2 2
1 1 1 1 1 1 1 2 2 2
1 1 1 1 1 3 2 2 2 2
1 1 1 1 3 3 3 2 2 2
3 3 3 3 3 3 3 3 2 2
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 2


//visited
1 1 1 2 3 3 2 1 1 1
1 1 1 1 2 3 3 2 1 1
1 2 1 1 2 3 3 2 1 1
2 2 1 1 1 2 3 3 2 1
3 3 2 1 2 3 4 3 2 1
4 4 3 2 3 3 4 3 2 1
5 5 4 3 2 2 3 4 3 2
5 4 3 2 1 1 2 3 4 3
5 4 3 2 1 1 1 2 3 4
6 5 4 3 2 2 2 3 4 5

 

상하 좌우로 비교하며 map 의 값이 다르고, visited 값이 최소인 값을 찾아줍니다. 저는 visited를 1부터 해서, 마지막에 2를 빼주었습니다.

 

# 제출 코드 

 

#include <iostream>
#include <queue>
#define MAXN 100
using namespace std;

int N;
int map[MAXN + 3][MAXN + 3];
int visited[MAXN + 3][MAXN + 3];
int land_num;
int xd[] = { 1, -1, 0, 0 };
int yd[] = { 0, 0, 1, -1 };
queue <pair<int, int>> q;

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}
}
void DFS(int y, int x) {
	if (map[y][x] != 1 || visited[y][x] != 0) return;
	visited[y][x] = 1;
	map[y][x] = land_num;
	q.push({ y, x });
	for (int i = 0; i < 4; i++) {
		int nx = x + xd[i];
		int ny = y + yd[i];
		// 범위 확인
		if (nx > 0 || nx <= N || ny > 0 || ny <= N) 
			DFS(ny, nx);
	}
	return;
}
void get_land() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] == 1 && visited[i][j] == 0) {
				land_num++;
				DFS(i, j);
			}
		}
	}
}
void BFS(){
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + xd[i];
			int ny = y + yd[i];
			// 범위 확인
			if (nx <= 0 || nx > N || ny <= 0 || ny > N) continue;
			if (map[ny][nx] == 0 && visited[ny][nx] == 0) {
				visited[ny][nx] = visited[y][x] + 1;
				map[ny][nx] = map[y][x];
				q.push({ ny, nx });
			}
		}
	}
	return;
}
int get_distance() { 
	BFS();
	int ans = -1;
	for(int i = 1; i<= N; i++){
		for(int j =1; j<=N; j++){
			for(int k = 0; k<4; k++){
				int x = j + xd[k];
				int y = i + yd[k];
				if( 0 < x && x <= N && 0 < y && y <=N){
					if(map[i][j] != map[y][x]){
						if(ans == -1 || ans > visited[i][j] + visited[y][x]){
							ans = visited[i][j] + visited[y][x];
						}
					}
				}
			}
		}
	}
	return ans - 2;
}
int main() {
	Input();
	get_land();
	int ans = get_distance();
	cout << ans;
}