이번 문제는 BFS를 활용하여 해결하였다. BFS를 통해 그룹을 만들고, BFS를 통해 다른 섬을 찾도록 하였다. 우선 섬들의 그룹을 만들어 순서대로 번호를 부여하였다. 그리고 각 섬에서 출발하여 같은 섬 번호의 좌표와 0을 거쳐 다른 섬 번호의 좌표를 만났을 때의 거리의 최솟값을 구하는 방식으로 해결하였다.

Code

from collections import deque
n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]
group = [[0 for _ in range(n)] for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def make_group(y, x, num):
    q = deque()
    q.append((y, x))
    group[y][x] = num
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < n and group[ny][nx] == 0 and grid[ny][nx] == 1:
                group[ny][nx] = num
                q.append((ny, nx))
def make_bridge(num):
    global answer
    dist = [[-1 for _ in range(n)] for _ in range(n)]
    q = deque()
    for i in range(n):
        for j in range(n):
            if group[i][j] == num:
                q.append((i, j))
                dist[i][j] = 0
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                if group[ny][nx] > 0 and group[ny][nx] != num:
                    answer = min(answer, dist[y][x])
                    return
                if group[ny][nx] == 0 and dist[ny][nx] == -1:
                    dist[ny][nx] = dist[y][x]+1
                    q.append((ny, nx))
answer = 1e9
num = 1
for i in range(n):
    for j in range(n):
        if grid[i][j] > 0 and not group[i][j]:
            make_group(i, j, num)
            num += 1
for i in range(1, num):
    make_bridge(i)
print(answer)