2146번 다리 만들기

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

---

아이디어

BFS를 두 번 돌려야 하는 문제이다.
1) 섬 구분하기 위한 BFS
2) 섬과 섬 사이의 최소 거리를 알기 위한 BFS

1) 섬 구분하기 위한 BFS

def BFS1(a, b): # 섬끼리 숫자 2부터 구분
    global cnt
    queue = deque()
    queue.append([a, b])
    graph[a][b] = cnt
    visited[a][b] = True

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n: continue
            if graph[nx][ny] == 1 and not visited[nx][ny]:
                graph[nx][ny] = cnt
                visited[nx][ny] = True
                queue.append([nx, ny])
    return
visited = [[False] * n for _ in range(n)]
cnt = 2
# 섬을 cnt로 구분(1씩 커져가며)
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            BFS1(i, j)
            cnt += 1

섬을 먼저 2부터 숫자 부여를 해준다. (섬끼리 구분하기 위해)
입력으로
1 1 0
0 0 1
0 0 1 이라고 하면
2 2 0
0 0 3
0 0 3 이렇게 된다.

2) 섬과 섬 사이의 최소 거리를 알기 위한 BFS

def BFS2(k): # 섬과 섬까지 거리가 측정
    global queue
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n: continue
            if graph[nx][ny] == 0 and checked[nx][ny] == 0:
                checked[nx][ny] = checked[x][y] + 1
                queue.append([nx, ny])
            elif graph[nx][ny] != k and checked[nx][ny] == 0:
                checked[nx][ny] = checked[x][y] + 1
    return max(map(max, checked))
queue = deque([])
max_value = max(map(max, graph)) # 섬의 개수를 알기 위해
result = float('inf')
for i in range(2, max_value+1): # 모든 섬을 다 돌기
    checked = [[0] * n for _ in range(n)] # 섬과 섬 사이의 거리를 측정하기 위함
    for j in range(n):
        for k in range(n):
            if graph[j][k] == i: # i인 섬 기준으로 BFS 돌기 위해 큐에 넣기
                queue.append([j, k])
    BFS2(i)
    for j in range(n):
        for k in range(n):
            if graph[j][k] != i and graph[j][k] != 0 and checked[j][k] != 0:
                result = min(result, checked[j][k] - 1) # 다른 섬인 애들 중에 가장 짧은 거리 찾기
print(result)

모든 섬을 다 BFS로 돌면서 거리를 측정해주고 최소 거리만 result에 저장해주며 갱신해야한다.
거리를 저장하는 리스트 checked를 따로 만들었고 2번 섬 탐색이 끝나면 초기화 하고, 3번 섬 탐색이 끝나면 초기화 하는 방식으로 계속 최솟값만 갱신해주었다.

---

코드

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

def BFS1(a, b): # 섬끼리 숫자 2부터 구분
    global cnt
    queue = deque()
    queue.append([a, b])
    graph[a][b] = cnt
    visited[a][b] = True

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n: continue
            if graph[nx][ny] == 1 and not visited[nx][ny]:
                graph[nx][ny] = cnt
                visited[nx][ny] = True
                queue.append([nx, ny])
    return

def BFS2(k): # 섬과 섬까지 거리가 측정
    global queue
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n: continue
            if graph[nx][ny] == 0 and checked[nx][ny] == 0:
                checked[nx][ny] = checked[x][y] + 1
                queue.append([nx, ny])
            elif graph[nx][ny] != k and checked[nx][ny] == 0:
                checked[nx][ny] = checked[x][y] + 1
    return max(map(max, checked))


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

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
visited = [[False] * n for _ in range(n)]
cnt = 2
# 섬을 cnt로 구분(1씩 커져가며)
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            BFS1(i, j)
            cnt += 1

queue = deque([])
max_value = max(map(max, graph)) # 섬의 개수를 알기 위해
result = float('inf')
for i in range(2, max_value+1): # 모든 섬을 다 돌기
    checked = [[0] * n for _ in range(n)] # 섬과 섬 사이의 거리를 측정하기 위함
    for j in range(n):
        for k in range(n):
            if graph[j][k] == i: # i인 섬 기준으로 BFS 돌기 위해 큐에 넣기
                queue.append([j, k])
    BFS2(i)
    for j in range(n):
        for k in range(n):
            if graph[j][k] != i and graph[j][k] != 0 and checked[j][k] != 0:
                result = min(result, checked[j][k] - 1) # 다른 섬인 애들 중에 가장 짧은 거리 찾기
print(result)