BOJ 2146 다리 만들기

📎Problem Link

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

2146번: 다리 만들기

 

📋 문제 정리

• 그래프에 1로 육지를, 0으로 바다를 나타냄. (그래프는 N X N)
• 1이 여러개 뭉쳐있는 곳을 섬 하나로 봄
• 한 섬과 다른 섬을 잇는 가장 짧은 다리 찾기
• 첫 줄에는 지도의 크기 N 입력 (N은 100 이하)
• 그 다음 줄부터 N개의 줄에는 0과 1로 바다와 육지를 입력함.

📌 예제 1

 

예제를 바탕으로 섬을 나누고 섬에 각각의 번호를 부여하면 위와 같다.  위의 예제에 대한 답은 3이며, 위의 빨간 색 표시가 최소로 연결할 수 있는 다리의 예시 중 하나이다.

 

🧐 Idea

• 기존에 0과 1로 바다와 육지만 나타나있는 map에서 각 섬마다 다른 번호를 부여해야함.
• 각 섬을 시작으로 DFS/BFS를 돌려 다른 번호의 섬을 만나면 즉시 종료.
• 각 육지에서 시작하여 연결한 다리 수 중 최솟값을 골라 return 함.

---

💻 Code

int main() {
	map bridge;
	int num = 1, result=10000;
	cin >> bridge.N;

	for (int i = 0; i < bridge.N; i++) {
		for (int j = 0; j < bridge.N; j++) {
			cin >> bridge.board[i][j];
		}
	} // 섬 입력

	for (int i = 0; i < bridge.N; i++) {
		for (int j = 0; j < bridge.N; j++) {
			if (!bridge.visited[i][j] && bridge.board[i][j])
				bridge.Area(i, j, num++);
		}
	} // 각 섬마다 번호 다르게 하기

	for (int i = 1; i < num; i++) {
		memset(bridge.visited, false, sizeof(bridge.visited));
		result=min(result, bridge.BFS(i));
	}

	cout << result << endl;
}

main 문은 쉬우니 가볍게 살펴보도록 하자. 위의 주석에서 볼 수 있다시피, 첫번째 이중 for문을 통해 board를 입력하고 두번째 이중 for문을 통해 각 섬마다 번호를 다르게 한다. 세번째 for문으로 BFS를 실행시켜 최소 다리를 구한다. 이 때 for문의 실행 범위는 1부터 num-1까지인데, 그 이유는 몇번에서 시작을 하든 num번 섬까지 가는 루트는 이미 탐색됐을 것이기 때문이다.

 

void Area(int y, int x, int num) {
		board[y][x] = num;
		visited[y][x] = true;
		for (int i = 0; i < 4; i++) {
			int nx = x + mx[i];
			int ny = y + my[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; //다음 좌표의 범위가 표를 벗어나면 다른 좌표로 변경

			if (!visited[ny][nx] && board[ny][nx]) //다음 좌표가 방문한 적이 없는 육지이면
			{
				Area(ny, nx, num); //다음 좌표 육지로 옮겨가기
			}
		}
	}

int BFS(int areanum) {
	queue <pair<int, int>> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == areanum) {
				visited[i][j] = true;
				q.push(make_pair(i, j));
			}
		}
	}
		int result = 0;
		while (!q.empty()) {
		int queuesize = q.size();
			for (int i = 0; i < queuesize; i++) {
			int y = q.front().first;
			int x = q.front().second;
			q.pop();
				for (int i = 0; i < 4; i++) {
				int ny = y + my[i];
				int nx = x + mx[i];
					if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
					if (board[ny][nx] && board[ny][nx] != areanum)
					return result;
				else if (!visited[ny][nx] && !board[ny][nx]) { //방문한 적 없는 바다면
					visited[ny][nx] = true;
					q.push(make_pair(ny, nx));
				}
			}
		}
		result++;
	}
}

먼저 Area함수를 보자. Area함수가 바로 각 섬마다 번호를 매기는 역할을 한다. 섬 번호는 main 문으로 부터 넘겨받아 섬 하나를 다 훑으면서 1을 섬 번호로 바꾼다. 

다음은 이 문제의 핵심인 BFS 함수이다. 먼저 area번에 해당하는 칸들을 queue에 모두 넣는다. 그 후 queue가 빌 때까지 현재 칸의 상하좌우를 살핀다. 만약 보고자 하는 칸이 다른 섬일 때, 한 섬까지 가는 다리를 이은 것이기 때문에 더 볼 필요가 없으므로 현재 result 값을 리턴한다. 방문한 적 없는 바다라면 queue에 추가한다. while문이 끝나기 전, 현재 칸에 다리를 만들었다는 뜻으로 result++을 실행한다.

---

이번 문제는 골드3인만큼 머리가 터질 것 같았다. Idea도 차근차근 잘 짰고, 코드도 차근차근 잘 짰는데 계속 에러가 나고 코드가 안 돌아서 몇일을 헤맸던 문제다. 결국 구글에서 search를 해서 풀 수 있었다. 사실 BFS에서 조금만 더 깊게 나아가면 풀 수 있었던 것 같은데 현재 내 머리의 한계였던 것 같다. 이 한계를 뿌시기 위해 더 심화된 BFS/DFS문제를 풀어봐야겠다.