BOJ 2146 다리 만들기

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

1. 문제요약

- 상하좌우로 연결된 섬이 여러개 있음

- 두 섬을 연결하는 최소 다리 길이는?

- 다리의 연결도 상하좌우

- 1 <= n <= 100

- 0은 바다 1은 육지

2. 접근방법

- dfs로 섬마다 번호를 붙임

- bfs로 섬을 한칸씩 확장해나가면서 다른섬을 만나면 다리길이를 비교하여 최소인 경우를 저장

3. 시간복잡도

- O(2n^2)

4. 회고

- queue를 쓰면서 생각지도 못한 경우가 발생함.......

- queue에 들어간 순서에 따라서 답이 달라질 수 있음

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

int n, map[101][101], dist[101][101];
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };
queue<pair<int, int> > q;

void dfs(int r, int c, int cnt){
	dist[r][c] = 1;
	map[r][c] = cnt;
	q.push(make_pair(r, c));

	for (int k = 0; k < 4; k++){
		int nr = r + dr[k];
		int nc = c + dc[k];

		if (0 <= nr && nr < n && 0 <= nc && nc < n && dist[nr][nc] == 0 && map[nr][nc] == 1){
			dfs(nr, nc, cnt);
		}
	}
}

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	int cnt = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (dist[i][j] == 0 && map[i][j] == 1)
				dfs(i, j, cnt++);

	bool isans = false;
	while (!q.empty() && !isans){
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++){
			int nr = r + dr[k];
			int nc = c + dc[k];

			if (0 <= nr && nr < n && 0 <= nc && nc < n){
				if (map[nr][nc] == 0){
					q.push(make_pair(nr, nc));
					map[nr][nc] = map[r][c];
					dist[nr][nc] = dist[r][c] + 1;
				}
                                // 가장 먼저 다른 섬을 발견하면 무조건 최소 다리 길이를 만족 할줄 알았는데 queue에 들어간 순서에 따라 답이 달라 질 수 있음. 반례는 아래 참조
				else if (map[nr][nc] != map[r][c]){
					cout << dist[r][c] + dist[nr][nc] - 2 << "\n";
					isans = true;
					break;
				}
			}
		}
	}

	return 0;
}

- 반례(답 2)

5

10001

00000

00000

00000

11001

인 경우 첫번째 행 좌우섬이 큐에 먼저 들어가기 때문에 아래 다리 2가 아닌 3이 출력됨

소스코드

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

int n, map[101][101], dist[101][101], ans = 987654321;
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };
queue<pair<int, int> > q;

void dfs(int r, int c, int cnt){
	dist[r][c] = 1;
	map[r][c] = cnt;
	q.push(make_pair(r, c));

	for (int k = 0; k < 4; k++){
		int nr = r + dr[k];
		int nc = c + dc[k];

		if (0 <= nr && nr < n && 0 <= nc && nc < n && dist[nr][nc] == 0 && map[nr][nc] == 1){
			dfs(nr, nc, cnt);
		}
	}
}

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	int cnt = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (dist[i][j] == 0 && map[i][j] == 1)
				dfs(i, j, cnt++);

	while (!q.empty()){
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++){
			int nr = r + dr[k];
			int nc = c + dc[k];

			if (0 <= nr && nr < n && 0 <= nc && nc < n){
				if (map[nr][nc] == 0){
					q.push(make_pair(nr, nc));
					map[nr][nc] = map[r][c];
					dist[nr][nc] = dist[r][c] + 1;
				}
				else if (map[nr][nc] != map[r][c] && dist[r][c] + dist[nr][nc] - 2 < ans){
					ans = dist[r][c] + dist[nr][nc] - 2;
				}
			}
		}
	}

	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]