# BOJ - 2146 - 다리 만들기

Updated:

``````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():
maps = []
for _ in range(N):

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

Categories:

Updated: