백준 2416 다리 만들기

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

가장 짧게 이을 수 있는 대륙을 찾는 문제이다.

가장 쉽게 접근할 수 있는 로직은

• 대륙별로 번호를 주기
• 각 대륙마다 bfs를 통해 다른 대륙까지 가는데 얼마나 걸리는지 체크
• 제일 가깝게 이을 수 있는 것 찾기

대륙별로 bfs를 통해 번호를 주었고,
대륙마다 bfs를 통해 다른 대륙을 찾는 것은 대륙의 원소들을 모두 큐에 넣고 큐의 크기만큼 반복문을 돌렸다. 한번 반복마다 한 칸을 이동한 것이다.

import copy
from collections import deque
n = int(input())
arr = []
for i in range(n):
    arr.append(list(map(int,input().split())))
cnt = 0
visited = [[0]*n for i in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
for i in range(n):
    for j in range(n):
        if arr[i][j] and not visited[i][j]:
            cnt += 1
            visited[i][j] = cnt
            q = deque([])
            q.append((i,j))
            while q:
                x,y = q.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if nx < 0 or nx >= n or ny < 0 or ny >= n:
                        continue
                    if arr[nx][ny] == 1 and not visited[nx][ny]:
                        visited[nx][ny] = cnt
                        q.append((nx,ny))
def bfs(count):
    q = deque([])
    for i in range(n):
        for j in range(n):
            if visited[i][j] == count:
                q.append((i,j))
    tmp = copy.deepcopy(visited)
    move = 0
    while q:
        qsize = len(q)
        move += 1
        while qsize:
            qsize -= 1
            x,y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or nx >= n or ny < 0 or ny >= n or tmp[nx][ny] == count:
                    continue
                if tmp[nx][ny] == 0:
                    tmp[nx][ny] = count
                    q.append((nx,ny))
                elif tmp[nx][ny] != count:
                    return move-1
ans = 99999
for i in range(1,cnt+1):
    ans = min(ans,bfs(i))
print(ans)