2146 - 다리 만들기

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

각 대륙마다 번호를 붙여서 동기적으로 대륙을 넓혀간다. 넓어가는 도중에 다른 대륙과 만난다면, 그 시점에 각 대륙이 넓혀진 거리만큼이 (부딪혔으므로) 연결된 거리이고, 그 중에 최소를 구한다.

동기적으로 넓혀가는 이유는 대륙 하나를 잡고 나머지와 비교하면 아래와 같은 경우가 생긴다.

대륙간의 거리를 모두 비교하면 \(O(N^2)\)이다. 물론 N이 최대 100까지이므로 모두 비교해도 문제될 건 없다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

int n, a[100][100];

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

bool visit[100][100];

bool giveId(int y, int x, const int id){
    if(y < 0 || y >= n || x < 0 || x >= n) return 0;
    
    if(visit[y][x] || a[y][x] == 0) return 0;
    visit[y][x] = true;
    
    a[y][x] = id;
    for(int i=0; i<4; ++i){
        giveId(y+dy[i], x+dx[i], id);
    }
    return 1;
}

struct land {
    int y, x, color;
};

int Distance[100][100];

int main(){
    scanf("%d ", &n);
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            scanf("%d", &a[i][j]);
            Distance[i][j] = a[i][j] ? 0 : INF;
        }
    }
    
    int color = 1;
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            color += giveId(i, j, color);
        }
    }
    
    queue<land> q;
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            if(a[i][j] != 0) continue;
            
            for(int d=0; d<4; ++d){
                int ny=i+dy[d], nx=j+dx[d];
                if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                if(0 != a[ny][nx]){
                    Distance[ny][nx] = min(Distance[ny][nx], 1);
                    q.push({i, j, a[ny][nx]});
                    break;
                }
            }
        }
    }
    
    int answer = 0;
    int dist = 0;
    while(!q.empty()){
        ++dist;
        int qs = q.size();
        while(qs--){
            int y = q.front().y;
            int x = q.front().x;
            int c = q.front().color;
            q.pop();
            
            if(a[y][x]) continue;
            a[y][x] = c;
            Distance[y][x] = dist;
            
            for(int d=0; d<4; ++d){
                int ny=y+dy[d], nx=x+dx[d];
                if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                
                if(a[ny][nx] == 0){
                    q.push({ny, nx, c});
                } else if(a[ny][nx] != c){
                    int expected = dist + Distance[ny][nx];
                    if(answer) answer = min(answer, expected);
                    else answer = expected;
                }
            }
        }
        if(answer > 0) break;
    }
    
    printf("%d", answer);
    
    return 0;
}