[백준 17472번] 다리 만들기 2 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
from heapq import heappush, heappop
dy = [1,-1,0,0]
dx = [0,0,1,-1]
INF = 10**6

N,M = map(int,input().split())

board = []
boundary = {}
for i in range(N):
  board.append([*map(int,input().split())])

def BFS(y,x,n):
  boundary[n] = []
  dq = deque([(y,x)])
  while dq:
    y,x = dq.popleft()
    if board[y][x] == n:
      continue
    board[y][x] = n
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0:
        if board[y1][x1] == 0:
          boundary[n].append((y,x,i))
        if board[y1][x1] == 1:
          dq.append((y1,x1))

def bridge(y,x,i,n):
  distance = 1
  while True:
    y1,x1 = y+dy[i]*distance,x+dx[i]*distance
    if not (N>y1>=0 and M>x1>=0):
      return
    if board[y1][x1]:
      break
    distance += 1
  n1 = board[y1][x1]
  if distance == 2 or n1 == n:
    return
  graph[n][n1] = graph[n1][n] = min(graph[n][n1],distance-1)

n = 1
for i in range(N):
  for j in range(M):
    if board[i][j] == 1:
      n += 1
      BFS(i,j,n)

nmax = n
graph = [[INF]*(nmax+1) for i in range(nmax+1)]

for n in boundary:
  for y,x,i in boundary[n]:
    bridge(y,x,i,n)

check = {i:0 for i in range(2,nmax+1)}
check[2] = 1
hq = []
for i in range(2,nmax+1):
  if graph[2][i] != INF:
    heappush(hq,(graph[2][i],i))

result = 0
for i in range(3,nmax+1):
  while hq:
    distance,n = heappop(hq)
    if check[n]:
      continue
    check[n] = 1
    result += distance
    for i in range(2,nmax+1):
      if check[i]:
        continue
      if graph[n][i] != INF:
        heappush(hq,(graph[n][i],i))
    break

succeed = True
for i in range(2,nmax+1):
  if check[i] == 0:
    succeed = False

if succeed:
  print(result)
else:
  print(-1)

 

MST 알고리즘을 알고 있다면 아이디어를 떠올리기 어렵지 않은 문제.

구현도 코드 길이가 길어서 그렇지 딱히 헷갈리거나 하는것도 없고 생각보다 간단하다.

다리가 교차하는 경우 다리 길이를 뺐었다면 문제가 까다로웠겠지만, 그게 아니어서 쉽게 해결하였다.

 

알고리즘을 요약하면

1. BFS 탐색으로 각 섬의 이름을 2~n으로 바꿔준다. 이때, 상하좌우에 0 즉 바다가 있는 경우, 이를 섬의 경계라고 보고, boundary list에 좌표와 방향을 저장한다.

2. boundary list에 저장한 방향과 좌표로 bridge 함수를 실행한다. bridge 함수는 방향대로 움직이다가 섬을 만나면 거리를 측정하는 함수

3. bridge 함수로 측정한 거리가 2 이상인 경우 도착한 섬의 이름에 대하여 해당 섬과의 그래프를 갱신

4. MST 알고리즘으로 최소거리 측정, 나는 프림 알고리즘을 사용하였다.

 

 

오늘의 교훈) MST 알고리즘은 유용하다