백준 2146. 다리 만들기

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

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

# 입력받기
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]

# 방향 벡터 (상, 하, 좌, 우)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 섬 구분하기
def mark_islands():
    island_id = 2  # 섬의 ID는 2부터 시작
    for i in range(N):
        for j in range(N):
            if board[i][j] == 1:  # 아직 방문하지 않은 섬
                bfs_mark_island(i, j, island_id)
                island_id += 1

def bfs_mark_island(x, y, island_id):
    queue = deque([(x, y)])
    board[x][y] = island_id
    while queue:
        cx, cy = queue.popleft()
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] == 1:
                board[nx][ny] = island_id
                queue.append((nx, ny))

# 다리 길이 계산
def find_shortest_bridge():
    shortest = float('inf')
    for i in range(N):
        for j in range(N):
            if board[i][j] > 1:  # 섬의 시작점
                shortest = min(shortest, bfs_shortest_bridge(i, j, board[i][j]))
    return shortest

def bfs_shortest_bridge(x, y, island_id):
    queue = deque([(x, y, 0)])  # 현재 위치와 거리
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True

    while queue:
        cx, cy, distance = queue.popleft()
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                visited[nx][ny] = True
                if board[nx][ny] == 0:  # 바다인 경우 계속 진행
                    queue.append((nx, ny, distance + 1))
                elif board[nx][ny] != island_id:  # 다른 섬에 도달한 경우
                    return distance
    return float('inf')  # 다른 섬에 도달하지 못한 경우

# 실행
mark_islands()  # 섬에 고유 ID 부여
result = find_shortest_bridge()  # 가장 짧은 다리 길이 계산
print(result)

[체크포인트]

1. board에서 1은 날것으로 두고 2부터 id를 매겨가면서 해당하는 모든 구역을 id로 바꿈 (bfs 이용)

2. 가장자리고 내부고 상관없이 섬의 모든 곳에서부터 시작해서 다른 섬으로 도달할 때까지 거리 매김(bfs 이용)

3. 그 거리를 매기는 함수에선 매번 돌릴 때마다 새로운 visitied 배열 이용(당연함.)

4. 거리 매길 때 다른 배열 만들지 않고 distance 변수를 추가해서 1씩 더해나감.

 

총 4개의 함수로 나누는 대장정을...그냥 감탄만 한다.