[C++][백준] - 다리 만들기 (2146번)

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

2146번: 다리 만들기

🔔 문제 : 

(1<= N <= 100)인 N*N의 지도가 주어집니다.

 

1은 섬, 0은 바다로 섬끼리 연결 할 수 있는 다리 1개의 최소 다리갯수를 구하는 문제입니다.

 

입력값으로 N값과, 지도 값들을 받습니다.

10
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

 

즉, 이러한 지도가 있다면

다리 3개가 각 섬들을 이어주는 최소개수의 다리입니다.

 

따라서 3을 출력하면 정답입니다.

---

🔔 Kick Point :

 

처음 생각한 방법은, DFS를 통하여 바다에 모든 다리를 놓을 수 있는 경우의 수를 두는 방법이였습니다.

하지만 N이 최대 100이기 때문에 모든 다리의 수를 구하는 행위는 어마무시한 연산량 때문에 할 수 없는 방법이였습니다.

 

그래서 두번째로 고안한 방법은.

 

BFS를 통하여 모든 섬에 라벨링을 한 뒤에

 

BFS를 통하여 하나의 섬을 기준으로 그 섬의 테두리방향으로 한칸씩 전진하여 다른 섬을 발견하는 방법이였습니다.

 

BFS를 만들 때, visited의 true라고 체크해야하는데 false 로 두고있어서 이것때문에 메모리 연산 초과가 나서 한참 해맸습니다. ㅠㅠ 다들 코드 잘 확인하시면 좋을 것 같아요.

 

 

1. 우선은 Labeling() 함수로 섬에 대한 라벨링을 시작합니다.

 

2. 그리고 각각의 섬에 대하여, BFS() 함수를 실행해 가장 짧은 섬을 발견하면 그 값을 리턴해줍니다.

 

3. 각 다리의 최솟값을 비교해가며 가장 최솟값을 출력해주면 됩니다.

---

🔔 Code :

#include <iostream>
#include <queue>
using namespace std;

// Variable
int n;
int map[100][100];
bool isVisited[100][100];
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

// 섬에 대한 라벨링
void Labeling(int y, int x, int label) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	map[y][x] = label;

	while (!q.empty()) {
		int _y = q.front().first;2
		int _x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = _y + dy[i];
			int nx = _x + dx[i];

			// 범위를 벗어난 경우, 한 번 지나온 곳을 가보는 경우
			if (ny < 0 || ny >= n || nx < 0 || nx >= n || map[ny][nx] != -1) continue;

			// 새로운 곳을 찾는 경우
			q.push({ ny,nx });
			map[ny][nx] = label;
		}
	}
}


// 한 섬에서, 다른 섬으로 가기까지의 최소거리 구하기 (섬에 대한 테두리를 만들어보리기)
int BFS(int label) {
	queue<pair<int, int>> q;
	
	// 한 섬에 대한 isVisited 채우기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == label) {
				isVisited[i][j] = true;
				// 한 섬에 대한 좌표 모두 큐에 넣기 
				q.push({ i,j });
			}
		}
	}


	// 테두리를 만들면서 다른 섬을 찾는 중입니다.
	int distant(0);
	while (!q.empty()) {
		int cnt = q.size();
		for (int i = 0; i < cnt; i++) {
			int _y = q.front().first;
			int _x = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++) {
				int ny = _y + dy[i];
				int nx = _x + dx[i];

				// 범위를 벗어난 경우 , 지나온 곳을 가보는 경우
				if (ny < 0 || ny >= n || nx < 0 || nx >= n || isVisited[ny][nx]) continue;

				// 섬을 발견한 경우
				if (map[ny][nx] != 0) {
					return distant;
				}
				// 바다만 발견한 경우
				else {
					q.push({ ny,nx });
					isVisited[ny][nx] = true;
				}
			}
		}
		distant++;
	}
	return 0;
	
}


int main() {
	cin >> n;
	int MIN = 10001;
	
	// Input
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int tmp; cin >> tmp;
			if (tmp == 1) map[i][j] = -1;
			else map[i][j] = 0;
		}
	}

	// 섬 라벨링
	int label = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == -1) {
				Labeling(i, j, label++);
			}
		}
	}

	// 각각의 섬에 대해서 다른섬 거리 찾기
	for (int i = 1; i < label; i++) {
		int tmp = BFS(i);
		MIN = MIN > tmp ? tmp : MIN;

		// isVisited 초기화;
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				isVisited[j][k] = false;
			}
		}
	}

	// Output
	cout << MIN;
}

---