문제
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.
이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.
위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.
물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).
지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.
입력
첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.
출력
첫째 줄에 가장 짧은 다리의 길이를 출력한다.
예제 입력 1
10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0예제 출력 1
3노트
- 먼저 서로 떨어진 섬들을 BFS로 탐색해서 서로 다른 섬으로 구분할 수 있도록 라벨링을 해야겠다.
- 그 다음에 구분된 섬들 위치를 전부 탐색 시작으로 잡고 multi bfs 돌려서 시작 섬의 라벨과 다른 섬에 도착할 때 dist 중에 가장 작은 값을 반환하면 될 것 같다.
- 그걸 모든 섬에서 돌리면 결과가 나올 듯?
#include <algorithm>
#include <iostream>
#include <queue>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)
#define MAX 101
int N;
int board[MAX][MAX];
int dist[MAX][MAX];
bool visited[MAX][MAX];
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
std::vector<std::pair<int, int>> area_mark(int r, int c, int area) {
board[r][c] = area;
visited[r][c] = true;
std::queue<std::pair<int, int>> Q;
std::vector<std::pair<int, int>> A;
Q.push({r, c});
// 같은 섬으로 라벨링 되는 위치는 벡터 넣어서 반환
// multi source BFS에서 한번에 큐에 넣으려고
A.push_back({r, c});
while (!Q.empty()) {
auto [qr, qc] = Q.front();
Q.pop();
for (int i = 0; i < 4; i++) {
int nr = qr + dr[i];
int nc = qc + dc[i];
if (0 <= nc && nc < N && 0 <= nr && nr < N) {
if (!visited[nr][nc] && board[nr][nc] == 1) {
board[nr][nc] = area;
visited[nr][nc] = true;
Q.push({nr, nc});
A.push_back({nr, nc});
}
}
}
}
return A;
}
int find_path(std::vector<std::pair<int, int>> &area) {
int dist[N][N];
int min_path = N * 2;
for (int r = 0; r < N; r++) {
std::fill(dist[r], dist[r] + N, 0);
}
std::queue<std::pair<int, int>> Q;
for (auto [r, c] : area) {
Q.push({r, c});
visited[r][c] = true;
}
while (!Q.empty()) {
auto [qr, qc] = Q.front();
Q.pop();
for (int i = 0; i < 4; i++) {
int nr = qr + dr[i];
int nc = qc + dc[i];
if (0 <= nc && nc < N && 0 <= nr && nr < N) {
if (!visited[nr][nc]) {
dist[nr][nc] = dist[qr][qc] + 1;
visited[nr][nc] = true;
// 바다인 지점은 다리를 놓고 또 나아가야하는 위치
if (board[nr][nc] == 0) {
Q.push({nr, nc});
}
// 탐색을 시작한 Source 섬의 라벨이 아닌 섬 번호만 조건에 넣고 싶은데,
// 그러러면 초기 시작 위치를 큐에 넣을 때 탐색 시작 섬의 라벨을 따로
// 보관해야함 근데 탐색 시작 후보로 넘어오는 area 파라미터의 모든
// pair가 전부 동일한 섬 라벨을 가리킨다는 보장을 할 수 없음 라벨링
// 로직 자체가 동일한 섬 라벨을 가리키는 페어만 넣어주긴 하지만 딱히
// 이 함수에서 그걸 검증하지 않으니까, 일반적으로 사용 가능한 함수는
// 아님 지금은 단순히 처음 큐에 넣을 때 visited도 true로 해주므로,
// visited = false이면서 0이 아닌 위치는 Source 섬이 아닌 다른
// 섬이라는 것을 알 수는 있음
else {
min_path = std::min(min_path, dist[qr][qc]);
}
}
}
}
}
return min_path;
}
void solve() {
std::cin >> N;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
std::cin >> board[r][c];
}
}
std::vector<std::vector<std::pair<int, int>>> areas;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (board[r][c] == 1 && !visited[r][c]) {
areas.push_back(area_mark(r, c, areas.size() + 1));
}
}
}
int min_path = N * 2;
for (auto area : areas) {
for (int r = 0; r < N; r++) {
std::fill(visited[r], visited[r] + N, false);
}
min_path = std::min(min_path, find_path(area));
}
std::cout << min_path;
}
int main() {
IO;
solve();
return 0;
}