[백준/C++] 2146. 다리 만들기

문제

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

각각의 섬(육지 덩어리?)에서 다른 섬 까지 갈 수 있는 모든 경우의 수 중에 최단 경로를 구하는 문제이다!

풀이

DFS와 BFS를 모두 이용했다.

먼저, 각 섬들의 번호를 구분하기 위해 DFS를 돌렸다.

그 후에 BFS를 돌려서 어떤 섬에서 또 다른 섬까지 갈 수 있는 모든 경우의 수를 구한 후에, 그 중에 최솟값을 출력했다. 

맵의 크기(n)이 100이하이기 때문에 input이 작아서 시간초과 걱정 없이 풀었다. 

코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

#define LAND 1
#define SEA 0 

int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int map[101][101] = { 0, };
bool visited[101][101] = { 0, };
int n;

void DFS(int r, int c, int num) {
	visited[r][c] = true;
	map[r][c] = num; //몇번 섬인지 표시
	for (int i = 0;i < 4;i++) {
		int next_r = r + dr[i];
		int next_c = c + dc[i];
		if (next_r >= n || next_r < 0 || next_c >= n || next_c < 0) continue;

		if (map[next_r][next_c] && !visited[next_r][next_c])
			DFS(next_r, next_c, num);
	}
}
int BFS(int cnt) {
	queue<pair<int, int>> q;

	//큐에 해당 번호의 섬의 좌표를 다 넣기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == cnt) {
				visited[i][j] = true;
				q.push(make_pair(i, j));
			}
		}
	}
	int result = 0;
	while (!q.empty()){
		int curSize = q.size();

		//현재 큐에 있는 칸에서 한칸씩 전진
		for (int i = 0; i < curSize; i++) {
			int r = q.front().first;
			int c = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int next_r = r + dr[i];
				int next_c= c + dc[i];

				//범위 내에 있는지 검사 
				if (0 <= next_r && next_r < n && 0 <= next_c && next_c < n) {
					//다른 섬에 도착하면 return
					if (map[next_r][next_c] && map[next_r][next_c] != cnt)
						return result;

					//방문하지 않은 바다이면 방문했다고 표시 후 큐에 넣기
					else if (map[next_r][next_c]  == SEA && !visited[next_r][next_c]) {
						visited[next_r][next_c] = true;
						q.push(make_pair(next_r, next_c));
					}
				}
			}
		}
		result++;
	}
}

int main(void) {
	cin >> n;
	for (int r = 0;r < n;r++) {
		for (int c = 0;c < n;c++) {
			cin >> map[r][c];
		}
	}
	int num = 1;
	for (int r = 0;r < n;r++) {
		for (int c = 0;c < n;c++) {
			if (map[r][c] == LAND && !visited[r][c]) {
				DFS(r, c, num);
				num++;
			}
		}
	}
	int min_dist = 987654321;
	for (int i = 1;i<num;i++) {
		fill(&visited[0][0], &visited[100][101], 0);
		min_dist = min(min_dist, BFS(i));
	}
	cout << min_dist << endl;
	return 0;
}

 

결과