🥚문제

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

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

🥚입력/출력

---

🍳코드

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


def mark_island(r, c, num):
    arr[r][c] = num
    q = deque([(r, c)])

    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if arr[nr][nc] > 0 and not visited[nr][nc]:
                    arr[nr][nc] = num
                    q.append((nr, nc))
                    visited[nr][nc] = True


def make_bridge(num):
    global ans

    dist = [[-1]*N for _ in range(N)]  # 거리가 저장되는 배열
    q = deque()

    for r in range(N):
        for c in range(N):
            # 번호 num인 섬에 속하는 좌표들을 q에 삽입
            if arr[r][c] == num:
                q.append((r, c))
                dist[r][c] = 0

    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                # 다른 섬
                if arr[nr][nc] > 0 and arr[nr][nc] != num:
                    ans = min(ans, dist[r][c])
                    return
                # 바다
                if arr[nr][nc] == 0 and dist[nr][nc] == -1:
                    dist[nr][nc] = dist[r][c] + 1
                    q.append((nr, nc))


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

dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]

# 가장 짧은 다리의 길이
ans = 10000

# 섬에 번호 매기기
visited = [[False]*N for _ in range(N)]
island_num = 1
for r in range(N):
    for c in range(N):
        # 섬을 1, 2, 3... 번호 매긴다
        if arr[r][c] == 1 and not visited[r][c]:
            mark_island(r, c, island_num)
            island_num += 1

# 다리 놓기
for i in range(1, island_num):
    make_bridge(i)

print(ans)

---

🧂아이디어

BFS

1. 지도의 크기와 데이터를 입력 받는다.

2. 서로 다른 섬을 구분짓기 위해 BFS를 통해 각각의 섬에 번호를 매긴다. 코드에서는 mark_island 함수로 이를 구현했다.

3. 번호 i로 표시된 섬(1 <= i < island_num)에서 다른 번호로 표시된 섬까지 이어지는 다리의 최소 길이를 BFS를 통해 각각 구하며 ans(가장 짧은 다리의 길이를 저장)를 갱신해간다. 코드에서는 make_bridge 함수로 이를 구현했다.

   • make_bridge 함수가 시작될 때 번호 i인 모든 섬의 좌표를 q에 넣고 bfs를 시작해준다.

참고: https://kyun2da.github.io/2021/04/22/makeBridge/