알고리즘 스터디 - 백준 2146번 : 다리 만들기(feat. Python)

문제 해석

• NxN 크기의 이차원 평면상에 여러 섬이 존재하고 있음
• 여기서 두 개의 섬을 이을 때 가장 짧은 다리의 길이를 출력하여야 함

어떤 알고리즘을 써야할까?

• 다리 만들기 2를 하고 나서 돌아와서 보니까 과정이 줄었다는 것을 알 수 있다.
• BFS로 섬을 구분하고 브루트 포스로 계산을 하면 되는 것이다.

알고리즘 코드

from collections import deque

n = int(input())
land = [list(map(int, input().split())) for _ in range(n)]

def bfs(x, y):
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    q = deque()
    q.append((x, y))

    coordinate = [(x, y)]
    land[x][y] = 0

    while q:
        x_, y_ = q.popleft()

        for i in range(4):
            new_x = x_ + dx[i]
            new_y = y_ + dy[i]

            if 0 <= new_x < n and 0 <= new_y < n and land[new_x][new_y] == 1:
                land[new_x][new_y] = 0
                q.append((new_x, new_y))
                coordinate.append((new_x, new_y))
    
    return coordinate

island = []

for i in range(n):
    for j in range(n):
        if land[i][j] == 1:
            island.append(bfs(i, j))

answer = 10001
for i in range(len(island)):
    for j in range(i+1, len(island)):
        for x, y in island[i]:
            for new_x, new_y in island[j]:
                answer = min(answer, abs(new_x-x) + abs(new_y-y))

print(answer-1)