[BaekJoon] 백준 2146번 다리 만들기

[BaekJoon] 백준 2146번 다리 만들기

 

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

 

내코드

 

- 어렵게 생각했지만 생각보다 간단했던 문제

- bfs 및 dfs로 풀수 있는 문제다.

- 알고리즘

1. 각 섬을 bfs로 돌며 1, 2, ... 라벨링 해준다. 즉, map에서 같은 섬은 같은 번호를 가지고 있다.

2. (섬의 개수 - 1)번 만큼 for문을 돌면서 각각의 섬 번호에 대해 bfs_search()함수를 돌려준다.

3. bfs_search() 함수가 1번 섬에 대해 도는 경우를 생각해보자.

3-1. 1번으로 라벨링된 지점을 모두 queue에 넣어준다.

3-2. queue가 빌때까지 상하좌우의 지점에 대해 만약 바다면 push해주는 것을 반복한다.

3-3. 바다가 아니고, 해당 섬 번호와 다른 섬 번호가 나오면 length값을 min_length에 넣어주고 return 해준다.

4. min_length 값을 출력해준다.

 

#include <string.h>
#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int n, min_length = 10000;
int** map;
bool** visited;
queue<pair<pair<int, int>, int>> qu; //x, y, length
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };


void bfs(int num) {
	while (!qu.empty()) {
		int x = qu.front().first.first;
		int y = qu.front().first.second;
		qu.pop();
		for (int i = 0; i < 4; i++) {
			int tmpx = x + dx[i];
			int tmpy = y + dy[i];
			if (tmpx < 0 || tmpx >= n || tmpy < 0 || tmpy >= n) continue;
			if (map[tmpx][tmpy] == 1 && visited[tmpx][tmpy] == false) {
				qu.push(make_pair(make_pair(tmpx, tmpy), 0));
				map[tmpx][tmpy] = num;
				visited[tmpx][tmpy] = true;
			}
		}
	}
}

void bfs_search(int num) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == num) {
				qu.push(make_pair(make_pair(i, j), 0));
				visited[i][j] = true;
			}
		}
	}
	while (!qu.empty()) {
		int x = qu.front().first.first;
		int y = qu.front().first.second;
		int length = qu.front().second;
		qu.pop();
		for (int i = 0; i < 4; i++) {
			int tmpx = x + dx[i];
			int tmpy = y + dy[i];
			if (tmpx < 0 || tmpx >= n || tmpy < 0 || tmpy >= n) continue;
			if (map[tmpx][tmpy] == num) continue;
			if (map[tmpx][tmpy] == 0 && visited[tmpx][tmpy] == false) {
				qu.push(make_pair(make_pair(tmpx, tmpy), length + 1));
				visited[tmpx][tmpy] = true;
			}
			if (map[tmpx][tmpy] != 0) {
				if (min_length > length) min_length = length;
				return;
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	map = new int* [n];
	visited = new bool* [n];
	for (int i = 0; i < n; i++) {
		map[i] = new int[n];
		visited[i] = new bool[n];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			visited[i][j] = false;
		}
	}
	int num = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && visited[i][j] == false) {
				qu.push(make_pair(make_pair(i, j), 0));
				map[i][j] = num;
				visited[i][j] = true;
				bfs(num);
				num++;
			}
		}
	}
	for (int k = 1; k <= num - 1; k++) {
		while (!qu.empty()) qu.pop();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				visited[i][j] = false;
			}
		}
		bfs_search(k);
	}
	cout << min_length;
	return 0;
}

 

 

참고