[2146] 다리 만들기

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

여러 개의 섬들을 잇는 다리중 가장 짧은 다리의 길이를 구하는 문제이다.

결국 문제를 해석하면 여러개의 컴포넌트가 주어지고 이 컴포넌트 사이의 가장 짧은 길이를 찾는 문제이다.

먼저 컴포넌트끼리의 구분을 지어야하기 때문에 DFS로 각 컴포넌트에 숫자를 부여했다.

그 후 최단 경로를 모든 섬 정점에서  BFS를 이용해 구하고 그 중 최솟값을 출력했다.

BFS를 수행할 때 각 섬들에게 번호를 부여하고 바다를 0 으로하여 만약 현재 정점의 섬 번호와 다른 섬 번호를 발견하면

거기서 BFS 종료를 시켜 현재 정점에서의 가장 가까운 섬까지의 거리를 계산하였다. 육지에서의 이동은 불 필요하므로

현재 보고있는 정점이 내 섬 번호와 같다면 더이상 진행하지 않고 바다일 때(0일 때)만 이동하게 했다.

문제 지문에서 알 수 있듯이 다리는 4방향으로 잇게 되므로 4방향 탐색으로 진행하면 된다.

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int n, cnt, mini;
int arr[110][110], land[110][110];
bool visit[110][110];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
bool isPossible(int x, int y) {
    return x >= 0 && y >= 0 && x<n&&y<n;
}
 
void dfs(int x, int y) {
    visit[x][y] = 1;
    land[x][y] = cnt;
    for (int i = 0; i<4; i++) {
        int nx = dx[i] + x;
        int ny = dy[i] + y;
        if (isPossible(nx, ny) && !visit[nx][ny] && arr[nx][ny] == 1) {
            dfs(nx, ny);
        }
    }
}
 
int bfs(int x, int y, int color) {
    queue<pair<int, int> > qu;
    qu.push({ x, y });
    visit[x][y] = 1;
    cnt = 0;
    while (int s = (int)qu.size()) {
        while (s--) {
            int cx = qu.front().first;
            int cy = qu.front().second;
            qu.pop();
            for (int i = 0; i<4; i++) {
                int nx = dx[i] + cx;
                int ny = dy[i] + cy;
                if (isPossible(nx, ny)) {
                    if (land[nx][ny] == color) continue;
                    if (land[nx][ny] != 0) return cnt;
                    if (!visit[nx][ny]) {
                        visit[nx][ny] = 1;
                        qu.push({ nx, ny });
                    }
                }
            }
        }
        cnt++;
    }
    return 0;
}
 
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    //dfs
    cnt = 1;
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            if (!visit[i][j] && arr[i][j] == 1) {
                dfs(i, j);
                cnt++;
            }
        }
    }
    //bfs
    mini = 987654321;
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            if (land[i][j] != 0) {
                memset(visit, 0, sizeof(visit));
                int r = bfs(i, j, land[i][j]);
                if (r != 0) mini = min(mini, r);
            }
        }
    }
 
    printf("%d\n", mini);
 
    return 0;
}