[백준] 다리 만들기 - python (2146번)

문제 해석

가능한 경우들을 탐색하며 최솟값을 찾는 문제이기 때문에 bfs로 접근하는 것이 합당하다고 생각하였습니당

접근 방법

1. 섬들의 정보를 미리 저장

섬들의 정보들을 담고 있는 islands 리스트를 만듭니다.
예를들어 주어진 2차원 배열(나라)이

a = [[1,1,0,0],
	 [1,0,0,0],
     [0,0,0,1],
     [0,0,1,1]]

이라면

islands = [[(0,0),(0,1),(1,0)],
		  [(2,3),(3,2),(3,3)]]

이 됩니다.

2. 각 섬들의 칸에서 주변 바다를 탐색

3. 다른 섬에 속하는 칸을 만나면 move count

4. 저장된 move count 보다 많아지면 탐색 중단

import sys
from collections import deque

input = sys.stdin.readline

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

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

def bound(x, y):
    return 0 <= x < N and 0 <= y < N

islands = []
f_visited = [[0] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if board[i][j] == 1 and f_visited[i][j] == 0:
            tmp = [(i, j)]
            q = deque()
            q.append((i, j))
            f_visited[i][j] = 1
            while q:
                x, y = q.popleft()
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if bound(nx, ny):
                        if board[nx][ny] == 1 and f_visited[nx][ny] == 0:
                            f_visited[nx][ny] = 1
                            q.append((nx, ny))
                            tmp.append((nx, ny))
            islands.append(tmp)

answer = N ** 2

for island in islands:
    for land in island:
        x = land[0]
        y = land[1]
        q = deque()
        # 초기 세팅
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if bound(nx, ny) and board[nx][ny] == 0:
                q.append((nx, ny, 0))
        if not q:
            continue
        else:  # 해안가면
            visited = [[0] * N for _ in range(N)]
            while q:
                x, y, move = q.popleft()
                if move > answer:
                    break
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if bound(nx, ny):
                        if board[nx][ny] == 0 and visited[nx][ny] == 0:
                            visited[nx][ny] = 1
                            q.append((nx, ny, move + 1))
                        elif board[nx][ny] == 1:
                            if (nx, ny) not in island:
                                answer = min(answer, move + 1)

print(answer)