[백준] 2146번 다리 만들기

해당 문제는 BFS를 활용한 구현 문제라고 볼 수 있다. 처음에 문제를 봤을 때는 많이 막막했지만 하나씩 생각하다보니 해결할 수 있었다. 가장 먼저 든 생각은 BFS를 활용한 거리 계산이다. 하지만 거리를 계산하기 위해서는 각각 섬들을 다르게 표시해야 한다. 표시를 했으면 이제 가장자리들로부터 시작하여 다른 섬까지의 거리를 계산한다.

정리하면

1. 섬들을 구분한다.

2. 해당 위치가 각 섬들의 가장자리인 경우에 BFS를 시작하여 다른 섬까지의 거리를 구한다.

3. 최솟값을 갱신해준다.

 

 

lcount는 섬의 갯수로 각 섬들을 구분할 때 쓰인다. 지도를 (0, 0)에서 (N-1, N-1)까지 확인하며 육지인 경우 BFS를 시작하여 해당 섬에 lcount값을 더해준다. 그렇게 되면 만약 섬이 3개인 경우 섬은 총 {2, 3, 4} 이렇게 3개가 될 것이다.

예를 들어,

0 1 0 0              0 2 0 0

1 1 0 1     -----> 2 2 0 3

0 0 0 1     -----> 0 0 0 3

1 1 0 0              4 4 0 0

이런 식으로 된다.

 

 

해당 지점이 섬의 가장자리인지 판별하기 위해 상,하,좌,우에 바다가 존재하는지 확인한다. 가장자리가 아니라면 상,하,좌,우 모두 육지일 것이고 가장자리라면 한 곳이라도 바다가 존재한다.

 

 

해당 지점이 가장자리면 BFS를 시작하여 다른 섬까지의 거리를 계산한다. 문제에서 다리의 길이를 물어봤으니 거리에서 1을 빼준 값으로 최솟값을 구한다.

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

vector<vector<int>> board(101, vector<int>(101)); // 지도
int N, answer;

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 lcount = 0; // 섬의 갯수

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			// 해당 칸이 육지일 경우
			if (board[i][j] == 1) {
				queue<pair<int, int>> q;
				lcount++;
				// lcount를 더해 섬을 구별해준다.
				// 1번째로 발견된 섬일 경우 lcount인 1을 더하여 2로 만들고
				// 2번째로 발견된 섬일 경우 lcount인 2를 더하여 해당 칸들을 3으로 만든다.
				board[i][j] += lcount;
				q.push(make_pair(i, j));

				while (!q.empty()) {
					auto cur = q.front();
					q.pop();

					for (int k = 0; k < 4; k++) {
						int xpos = cur.first + dx[k];
						int ypos = cur.second + dy[k];

						if (xpos < 0 or xpos >= N or ypos < 0 or ypos >= N)
							continue;
						// 이미 칸을 방문하여 업데이트한 경우와 바다인 경우는 continue 한다.
						if (board[xpos][ypos] > 1 or board[xpos][ypos] == 0)
							continue;
						board[xpos][ypos] += lcount;
						q.push({ xpos,ypos });
					}
				}
			}
		}
	}

	answer = 1000000;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			// 바다인 경우 continue
			if (board[i][j] == 0)
				continue;
			// 해당 위치가 가장자리인지 판별
			bool isbound = false;
			for (int k = 0; k < 4; k++) {
				int xpos = i + dx[k];
				int ypos = j + dy[k];

				if (xpos < 0 or xpos >= N or ypos < 0 or ypos >= N)
					continue;
				// 한 곳이라도 바다가 있으면 가장자리이므로 break
				if (board[xpos][ypos] == 0) {
					isbound = true;
					break;
				}
			}
			// 가장자리가 아니면 continue
			if (!isbound)
				continue;

			queue<pair<int, int>> q;
			vector<vector<int>> dis(101, vector<int>(101, 0)); // 시작 위치로부터의 거리
			vector<vector<bool>> visited(101, vector<bool>(101, false)); // 방문 여부
			q.push({ i,j });
			visited[i][j] = true;

			while (!q.empty()) {
				auto cur = q.front();
				q.pop();

				// 시작 섬과 다른 섬이고 해당 위치가 바다가 아닌 경우 다른 섬에 도착한것이다.
				if (board[cur.first][cur.second] != board[i][j] and board[cur.first][cur.second] > 0) {
					answer = min(dis[cur.first][cur.second] - 1, answer);
					break;
				}

				for (int k = 0; k < 4; k++) {
					int xpos = cur.first + dx[k];
					int ypos = cur.second + dy[k];

					if (xpos < 0 or xpos >= N or ypos < 0 or ypos >= N)
						continue;
					// 현재 위치가 시작 섬에 포함되거나 이미 방문한 바다인 경우
					if (board[xpos][ypos] == board[i][j] or visited[xpos][ypos])
						continue;
					visited[xpos][ypos] = true;
					dis[xpos][ypos] = dis[cur.first][cur.second] + 1;
					q.push({ xpos,ypos });
				}
			}
		}
	}

	cout << answer;

	return 0;
}