각 대륙마다 번호를 붙여서 동기적으로 대륙을 넓혀간다. 넓어가는 도중에 다른 대륙과 만난다면, 그 시점에 각 대륙이 넓혀진 거리만큼이 (부딪혔으므로) 연결된 거리이고, 그 중에 최소를 구한다.
동기적으로 넓혀가는 이유는 대륙 하나를 잡고 나머지와 비교하면 아래와 같은 경우가 생긴다.
#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;
}
