Baekjoon Online Judge 2146번 파이썬 😩

문제링크
https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

bfs를 두번 쓰는 문제는 처음이라 어려웠다.
한 섬에서 다른 섬으로 가는 최단 거리를 찾는 문제다.
그래서 이 문제에서 해야 할 일은 섬 구분하기, 최단 거리 찾기가 있다.
이를 위해 bfs를 두번 사용해야한다.

나중에 한번 더 풀어봐야 할 문제다.
정답 코드

import sys
from collections import deque
  
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs_numbering(x,y):
  global count
  queue = deque()
  queue.append((x,y))
  visited[x][y] = True
  mapping[x][y] = count

  while queue:
    x,y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<N and 0<=ny<N:
        if mapping[nx][ny] == 1 and visited[nx][ny] == False:
          visited[nx][ny] = True
          mapping[nx][ny] = count #섬 넘버링
          queue.append((nx,ny))

def bfs_bridge(z):
  global result 
  q = deque()

  distance = [[-1]*N for i in range(N)] #거리
  for i in range(N):
    for j in range(N):
      if mapping[i][j] == z:
        q.append((i,j))
        distance[i][j] = 0 #섬 내부라서 거리는 0

  while q:
    x,y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<N and 0<=ny<N:
        if mapping[nx][ny] == 0 and distance[nx][ny] == -1: #바다
          distance[nx][ny] = distance[x][y] + 1 #거리를 1씩 증가시키면서
          q.append((nx,ny))
        if mapping[nx][ny] != 0 and mapping[nx][ny] != z: #다른 섬 도착
          result = min(result,distance[x][y]) 
          return #다른 섬을 만나면 함수 실행을 끝내야함.

N = int(sys.stdin.readline())
mapping = []
for i in range(N):
  mapping.append(list(map(int,sys.stdin.readline().split())))


visited = [[False]*N for i in range(N)]  
count = 1
result = sys.maxsize #다리의 길이가 얼마가 될지 모르므로 가장 큰 정수로 할당하여 min으로 비교할 수 있게한다.

for i in range(N):
  for j in range(N):
    if visited[i][j] == 0 and mapping[i][j] == 1:
      bfs_numbering(i,j)
      count += 1

for i in range(1,count):
  bfs_bridge(i)

print(result)