백준 2146 다리 만들기

from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
check = [[-1] * n for _ in range(n)]

def bfs(i, j):
    outer = []
    q = deque()
    q.append((i, j))
    check[i][j] = 0
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                if (x, y) not in outer:
                    outer.append((x, y))
                continue
            if check[nx][ny] == -1:
                if g[nx][ny] == 0:
                    if (x, y) not in outer:
                        outer.append((x, y))
                else:
                    q.append((nx, ny))
                    check[nx][ny] = 0
    return outer

Island = []
for i in range(n):
    for j in range(n):
        if check[i][j] == -1 and g[i][j] == 1:
            Island.append(bfs(i, j))
            
ans = n * n + 1
for i in range(len(Island)-1):
    for j in range(i+1, len(Island)):
        for x1, y1 in Island[i]:
            for x2, y2 in Island[j]:
                ans = min(ans, abs(x1-x2)+abs(y1-y2) - 1)

print(ans)

bfs로 경계부분을 구해서 경계~경계까지 거리의 최소값을 구한다