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

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

2146번: 다리 만들기

 

BFS 문제다.

 

처음 떠올린 방법은 덩어리를 찾아 덩어리 별로 같은 숫자로 저장하는 것이다.

그 후 각 덩어리의 테두리로부터 본인 숫자보다 큰 덩어리에 닿는 경우의 수를 모두 찾은 후 최솟값을 출력하는 것이다.

 

시간이 오래 걸릴 것 같아 최대한 반복을 덜 돌리려고 고민을 했다.

모든 경우의 수를 찾지 않고, 다리의 최소 길이보다 이동 수가 많아지면 함수를 바로 종료하는 것이다.

그리고 테두리를 따로 구분하지 않아도 방문 배열로 인해 바로 함수가 종료되기에 이 부분은 생략해도 될 것 같다.

 

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

int n, mini = 10001;
int board[1000][1000];
bool visit[1000][1000];

// 상하좌우 탐색을 위함
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

// 섬(덩어리)을 구분해주기 위한 BFS
void BFS(int g, int r, int c) {
	// <r, c>
	queue<pair<int, int>> q;

	board[r][c] = g;
	q.push({ r, c });

	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		int curr = q.front().first;
		int curc = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int rr = curr + dr[i];
			int cc = curc + dc[i];			

			// 범위를 벗어나면 continue
			if (rr < 0 || cc < 0 || rr >= n || cc >= n) continue;
			
			// 육지가 아니거나 이미 탐색한 섬이라면 continue
			if (board[rr][cc] != 1) continue;

			board[rr][cc] = g;
			q.push({ rr, cc });
		}
	}
}

// 가장 짧은 다리를 찾기 위한 함수
void search(int r, int c) {
	// <length, <r, c>>
	queue<pair<int, pair<int, int>>> q;

	q.push({ 0, {r, c} });
	visit[r][c] = 1;

	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		int curr = q.front().second.first;
		int curc = q.front().second.second;
		int move = q.front().first;

		q.pop();

		// 이동 횟수가 최솟값 이상이라면 함수 종료
		if (move >= mini) return;

		for (int i = 0; i < 4; i++) {
			int rr = curr + dr[i];
			int cc = curc + dc[i];

			// 범위를 벗어나면 continue
			if (rr < 0 || cc < 0 || rr >= n || cc >= n) continue;
			
			// 방문한 적이 있으면 continue
			if (visit[rr][cc]) continue;
			
			// 파라미터로 받은 섬과 움직이는 곳의 섬이 같은 섬이면 continue
			if (board[rr][cc] == board[r][c]) continue;

			// 본인의 섬 숫자보다 큰 섬에 도착했다면 종료
			if (board[rr][cc] > board[r][c]) {
				// 이동 횟수 (다리 길이)가 앞서 구한 최소값보다 작으면 저장
				if (move < mini) mini = move;
				return;
			}

			q.push({ move + 1, {rr, cc} });
			visit[rr][cc] = 1;
		}
	}
}

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> board[i][j];

	// 섬을 구분하기 위함
	int g = 2;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (board[i][j] == 1) BFS(g++, i, j);

	// 다리 길이의 최솟값을 찾기 위함
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			memset(visit, false, sizeof(visit));
			if (board[i][j]) search(i, j);
		}

	cout << mini;
}

주석 달고 코드 건드렸는지 확인하기 위해서 코드를 한 번 더 돌려보는데

아래는 주석 없이, 위에는 주석을 달고 제출을 한 결과다.

메모리와 시간이 왜 줄었는지 의문이다...