2146번: 다리 만들기

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


$O(n^2)$

섬마다 다르게 표시해놓고 섬의 각 지점을 큐에 넣고 BFS를 돌려 다른 섬간 최단 거리를 구한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, b[100][100], d[100][100], c, r = 1e9;
queue<pair<int, int> > q;
void f(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= n || !d[x][y]) return;
    d[x][y] = 0;
    b[x][y] = c;
    q.push({ x,y });
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) scanf("%d", d[i] + j);
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) if (d[i][j]) ++c, f(i, j);
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = x + fx[i], ty = y + fy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= n) continue;
            if (b[tx][ty]) {
                if (b[tx][ty] ^ b[x][y] && r>d[tx][ty] + d[x][y]) r = d[tx][ty] + d[x][y];
                continue;
            }
            b[tx][ty] = b[x][y];
            d[tx][ty] = d[x][y] + 1;
            q.push({ tx,ty });
        }
    }
    printf("%d", r);
    return 0;
}