Python - 다리 만들기 (2146) BFS

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

2146번: 다리 만들기

 - 큐에 넣는 경우의 수

    1) 다리가 만들어지지 않았다면 큐에 저장

 

1. 섬이 모두 1로 입력을 받으니 따로 섬을 구분하고 섬의 위치를 큐에 저장합니다.

2. 각 섬에서 모든 방향으로 다리를 놓습니다.

3. 다른 섬에서부터 만든 다리를 만난다면 정답을 저장합니다. (최솟값으로)

 

갔던 곳은 다시 되돌아가지 않으므로 시간복잡도는 O(n²)

import sys
from collections import deque
input = sys.stdin.readline
a = []
que = deque()
que2 = deque()
dire = [[-1, 1, 0, 0], [0, 0, -1, 1]]
freq = [[0 for i in range(100)] for j in range(100)]

def BFS(x, y, key):
    global n
    que.clear()
    que.append((x, y))
    que2.append((x, y))
    freq[x][y] = 1
    a[x][y] = key

    while que:
        ax, ay = que.popleft()

        for i in range(4):
            tx, ty = dire[0][i] + ax, dire[1][i] + ay
            if not (0 <= tx < n and 0 <= ty < n): continue
            if freq[tx][ty] or not a[tx][ty] : continue
            freq[tx][ty] = 1
            a[tx][ty] = key
            que.append((tx, ty))
            
            # 섬의 위치를 모두 두 번째 큐에 저장 해놓습니다.
            que2.append((tx, ty))


n = int(input().strip())
for i in range(n):
    a.append(list(map(int, input().strip().split())))

# 섬의 이름을 정합니다.
key = 2
for i in range(n):
    for j in range(n):
        if a[i][j] and not freq[i][j]:
            BFS(i, j, key)
            key += 1

ans = 0x7fffffff
while que2:
    x, y = que2.popleft()
    for i in range(4):
        tx, ty = x + dire[0][i], y + dire[1][i]
        if not (0 <= tx < n and 0 <= ty < n): continue
        
        # tx, ty 좌표에 바다가 아니고 다른 섬의 다리와 만났을 때 답 갱신
        if freq[x][y] * freq[tx][ty] and a[x][y] != a[tx][ty] :
            ans = min(ans, freq[x][y] + freq[tx][ty] - 2)
        if freq[tx][ty]: continue

        freq[tx][ty] += freq[x][y] + 1
        a[tx][ty] = a[x][y] # 다리놓기
        que2.append((tx, ty))
print(ans)