[Python/파이썬] 백준 2146 - 다리 만들기

문제 설명

입력과 출력 및 예제

---

풀이 코드

이 문제를 풀기 위해서는 두 단계의 BFS를 사용하여 섬을 구분 짓고, 각 섬까지의 거리를 측정하여 최단 거리를 찾는 방법으로 구현하였다.

1. 첫 번째 BFS(각 섬에 번호를 부여): 섬의 개수를 파악하고 각 섬의 영역을 식별하기 위해, BFS 알고리즘을 사용하여 섬에 고유한 번호를 부여한다. 
2. 두 번째 BFS(각 섬에서 다리를 놓아 도달 가능한 다른 섬까지의 거리를 측정): 섬의 땅 덩어리에서 다리를 놓기 시작하여, 다른 섬에 도달할 때까지 다리의 길이를 카운트한다. 이 때, BFS를 사용하여 땅 덩어리에서 시작하여 조건에 맞는 이동을 반복하며, 이동 거리를 업데이트한다.

 

정답 코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
maps = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

# 섬의 개수를 구하고 섬마다 번호를 표시하는 bfs
def bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    maps[x][y] = mark

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if maps[nx][ny] == 1:
                    q.append((nx, ny))
                    maps[nx][ny] = mark
                    visited[nx][ny] = True

# 섬 사이 최단거리를 구하는 bfs
def bfs2(island):
    q = deque()
    dist = [[-1] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if maps[i][j] == island:
                q.append((i, j))
                dist[i][j] = 0
    
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < n and 0 <= ny < n:
                if maps[nx][ny] != island and maps[nx][ny] != 0: # 다른 섬과 만났을 경우
                    return dist[x][y]
                if maps[nx][ny] == 0 and dist[nx][ny] == -1: # 물이고 아직 건너지 않은 곳일 경우
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))

mark = 1 # 섬마다 번호를 체크하기 위한 값
for x in range(n):
    for y in range(n):
        if maps[x][y] == 1 and not visited[x][y]:
            island_cnt = bfs(x, y)
            mark += 1

result = sys.maxsize # 최솟값을 구하기 위해 가장 큰 값으로 세팅
for island in range(1, mark):
    result = min(result, bfs2(island))

print(result)