[백준][BFS][그룹화] 2146. 다리만들기

2146. 다리만들기

채점 현황

 

• 내 풀이
  • 연결된 섬끼리 그룹화
  • 섬 사이 거리 계산 한 후에 각각의 섬끼리의 최소거리 저장
  • 다리 하나만 있으면 되므로 그 중에 최솟값

from collections import deque

#그룹화
def group(i, j):
    global cnt
    lst[i][j] = cnt
    queue.append((i, j))
  
    while queue:
        x, y = queue.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: continue
            if graph[nx][ny] == 0: continue
            
            if lst[nx][ny] == 0:
                lst[nx][ny] = cnt
                queue.append((nx, ny))

#거리체크
def bfs(i, j, num):
    visited[i][j] = 0
    queue.append((i, j, num))
    
    while queue:
        x, y, num = queue.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: continue
            if graph[nx][ny] == 1: #섬 일때
                to = lst[nx][ny]
                if num != to: #다른 그룹이면 
                    #두 그룹 사이 거리 업데이트
                    check[num][to] = min(check[num][to], visited[x][y])
                continue

            #거리가 더 가까우면 업데이트
            if visited[nx][ny] > visited[x][y] + 1:
                visited[nx][ny] = visited[x][y] + 1
                queue.append((nx, ny, num))


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

lst = [[0 for _ in range(n)] for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()

#그룹 짓기
cnt = 0
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1 and lst[i][j] == 0:
            cnt += 1
            group(i, j)

#각 그룹사이의 최소거리
check = [[int(1e9) for _ in range(cnt+1)] for _ in range(cnt+1)]

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            visited = [[int(1e9) for _ in range(n)] for _ in range(n)]
            num = lst[i][j] #그룹번호 넘겨주기
            bfs(i, j, num)

#한 그룹만 연결하면 되므로 거리 중 최소값 구하기
result=int(1e9)
for i in range(cnt+1):
    result=min(result, min(check[i]))

print(result)