BOJ - 2146 - 다리 만들기

import sys
from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def init(maps, temp, i, j, w, N):
    dq = deque()
    dq.append((i, j))
    maps[i][j] = (w * -1)

    while dq:
        x, y = dq.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if maps[nx][ny] == 1:
                    maps[nx][ny] = (w * -1)
                    dq.append((nx, ny))
                elif maps[nx][ny] == 0 and (x, y) not in temp:
                    temp.append((x, y))

def BFS(maps, ocean, N):
    w = 0
    ret = 1e9
    while ocean:
        w += 1
        for _ in range(len(ocean)):
            x, y = ocean.popleft()
            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if 0 <= nx < N and 0 <= ny < N:
                    if maps[nx][ny] == 0:
                        maps[nx][ny] = maps[x][y]
                        ocean.append((nx, ny))
                    elif maps[nx][ny] < maps[x][y]:
                        ret = min(ret, (w - 1) * 2)
                    elif maps[nx][ny] > maps[x][y]:
                        ret = min(ret, w * 2 - 1)
    return ret

def solution():
    N = int(sys.stdin.readline())
    maps = []
    for _ in range(N):
        maps.append(list(map(int, sys.stdin.readline().split())))

    ocean = deque()
    idx = 1
    for i in range(N):
        for j in range(N):
            if maps[i][j] == 1:
                init(maps, ocean, i, j, idx, N)
                idx += 1
    print(BFS(maps, ocean, N))
solution()

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