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

유후·2022년 5월 23일
0

백준

목록 보기
35/66

📌 문제

BOJ 바로가기

섬에서 다른 섬까지 다리를 하나 건설할 때, 다리의 길이의 최솟값을 구해야 한다.

🗡 풀이

📍 몇시간동안 이 문제만 붙잡고 있었다. 분명 로직은 완벽한데 자꾸 이상한 값이 나와서... 몇시간동안 디버깅한 결과 찾은 오류의 원인은 .. 큐를 비워주지 않아서 생겼던 것이었다 ㅋㅋㅋㅋㅋ BFS함수가 중간에 return되도록 만들어줬기 때문에 함수가 끝날 때마다 큐를 비워줬어야 했다. 그동안 중간에 return 되고, 여러번 호출되는 BFS 문제를 풀어본 적이 없어서 이번에 한참 헤맸다. 진짜 두번 다시 같은 오류를 겪고 싶지 않다..

📍 섬에 라벨링을 해준다. (단지 번호 붙이기 문제와 유사하다.) cnt를 1로 초기화해주고 dfs함수가 호출될 때마다 cnt를 1씩 늘려주며 라벨링했다.
📍 섬의 가장자리인지 아닌지를 판별하는 함수를 만들어주었다. 다음 소스코드의 is_edge 함수가 그 역할을 한다.
📍 섬의 가장자리에서 bfs 탐색을 시작한다. bfs 함수는 다른 섬을 만날 때까지 dist 배열에 거리 값을 채워주는 역할을 한다. 이 때, 모든 섬의 가장자리 전부에서 bfs함수를 호출해주어야 한다. 이렇게 얻은 거리들 중 최솟값이 답이 된다.
📍 bfs함수가 여러 번 호출되기 때문에 초기화에 신경을 써줘야 한다.

🚩 소스코드

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int map[100][100];
int dist[1001][1001] = { 0 };
bool visited[100][100];
queue <pair<int, int>> q;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int n, min_dist = 10001;

// 섬 넘버링
void dfs(int x, int y, int cnt) {
	visited[x][y] = true;
	map[x][y] = cnt;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < n && !visited[nx][ny] && map[nx][ny])
			dfs(nx, ny, cnt);
	}
}

// 섬의 가장자리인지 체크
bool is_edge(int x, int y, int cnt) {
	for (int i = 0; i < 4; i++) {
		int cx = x + dx[i];
		int cy = y + dy[i];
		if (0 <= cx && cx < n && 0 <= cy && cy < n && map[x][y] == cnt && map[cx][cy] == 0)
			return true;
	}
	return false;
}

// 다리 최소 길이 구하기
void bfs(int x, int y, int cnt) {
	q.push({ x, y });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && !visited[nx][ny]) {
				// 바다 항해중
				if (map[nx][ny] == 0) {
					q.push({ nx, ny });
					visited[nx][ny] = true;
					dist[nx][ny] = dist[x][y] + 1;
				}
				// 다른 섬 도착
				else if (map[nx][ny] != cnt) {
					dist[nx][ny] = dist[x][y];
					min_dist = min(dist[nx][ny], min_dist);
					while (!q.empty()) // 큐 비워주기!!!!!!
						q.pop();
					return;
				}
			}
			
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	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 (!visited[i][j] && map[i][j])
				dfs(i, j, cnt++);
		}
	}
	// 다리 최소 길이 구하기(모든 섬 -> 섬 체크)
	int mini = 10001;
	for (int i = 1; i < cnt; i++) {
		for (int a = 0; a < n; a++) {
			for (int b = 0; b < n; b++) {
				if (is_edge(a, b, i)) { // 섬의 가장자리에서 출발하는 BFS
					memset(visited, false, sizeof(visited));
					memset(dist, 0, sizeof(dist));
					bfs(a, b, i);
				}
			}
		}
	}
	// 결과 출력
	cout << min_dist;
}
profile
이것저것 공부하는 대학생

0개의 댓글