[백준] 2146번 - 다리 만들기 (파이썬)

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

# 다리 만들기
from collections import deque
import sys
input = sys.stdin.readline
MAX = sys.maxsize

N = int(input())
arr = []
sea = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(N):
        if arr[i][j] == 0:
            sea.append((i, j))

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


def bfs(a, b):
    global result
    q = deque()
    q.append((a, b))
    visited = [[0] * N for _ in range(N)]
    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 and visited[nx][ny] == 0:
                if arr[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))
                elif arr[nx][ny] == 1:
                    if check_land(a, b, nx, ny):
                        result = min(result, visited[x][y])
                        return


def check_land(a1, b1, a2, b2):
    q = deque()
    q.append((a1, b1))
    visited = [[False] * N for _ in range(N)]
    visited[a1][b1] = True
    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 and not visited[nx][ny]:
                if arr[nx][ny] == 1:
                    visited[nx][ny] = True
                    q.append((nx, ny))
    if visited[a2][b2]:
        return False
    else:
        return True


for a, b in sea:
    can = False
    for k in range(4):
        na = a + dx[k]
        nb = b + dy[k]
        if 0 <= na < N and 0 <= nb < N:
            if arr[na][nb] == 1:
                a = na
                b = nb
                can = True
    if can:
        bfs(a, b)
print(result)

 

BFS

1. 입력을 받으면서 바다인 위치를 따로 sea리스트에 넣는다

2. 바다인 sea리스트를 전부 확인하면서 상하좌우가 땅(1)이면 그위치를 bfs로 탐색을 시작

    - bfs : 상하좌우가 바다(0)인 부분으로만 이동한다. 가장 처음 땅(1)이 나오면 check_land실행

    - check_land : 처음 시작한 땅과 도착한 땅이 같은 대륙인지 아닌지 확인한다. 같은대륙이면 True리턴

    - bfs : check_land가 True이면 현재 길이와 result의 최솟값으로 result 초기화

3. result 출력

 

땅의 가장자리를 리스트에 넣어서 bfs탐색을 시작하는 것이 중요하다

또 같은 대륙인지 다른 대륙인지 판단하는 것도 중요하다