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

1. 코드

import copy
import sys
from collections import deque, defaultdict

def check(x, y):
    add = False
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < n:
            if ground[nx][ny] == 0:
                add = True
    return add


ans = 99999999
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n = int(sys.stdin.readline().rstrip())
ground = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
continent = copy.deepcopy(ground)

num = 2
d = defaultdict(list)
for i in range(n):
    for j in range(n):
        if continent[i][j] == 1:
            flag = False
            Q = deque()
            Q.append((i, j))
            while Q:
                x, y = Q.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < n and 0 <= ny < n:
                        if continent[nx][ny] == 1:
                            flag = True
                            if check(nx, ny):  # 가장자리 check
                                d[num].append((nx, ny))
                            continent[nx][ny] = num
                            Q.append((nx, ny))
            if not flag:
                continent[i][j] = num
                d[num].append((i, j))
            num += 1


for k in d:
    flag = False
    dis = [[-1] * n for _ in range(n)]
    q = deque(d[k])
    for i in range(n):
        for j in range(n):
            if continent[i][j] == k:
                dis[i][j] = 0
    while q:
        x, y = q.popleft()
        if flag:
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if continent[nx][ny] == 0 and dis[nx][ny] == -1:
                    dis[nx][ny] = dis[x][y] + 1
                    q.append((nx, ny))
                elif continent[nx][ny] != k and continent[nx][ny] != 0:
                    flag = True
                    ans = min(ans, dis[x][y])
                    break
print(ans)