[백준 1109번] 섬 (Python3)

import sys
input = sys.stdin.readline
from collections import *
dy = [1,-1,0,0,1,1,-1,-1]; dx = [0,0,1,-1,1,-1,1,-1]

def DFS(ocean):
  island = set(); h = 0
  for y,x in ocean:
    if not visited[y][x]:
      island |= BFS(y,x,4,0)
  for y,x in island:
    if not visited[y][x]:
      h = max(h,DFS(BFS(y,x,8,1))+1)
  if len(result)==h:
    result.append(0)
  result[h] += 1
  return h

def BFS(y,x,d,n):
  dq = deque([(y,x)]); S = set()
  while dq:
    y,x = dq.popleft()
    if visited[y][x]:
      continue
    visited[y][x] = 1
    for i in range(d):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0 and not visited[y1][x1]:
        if board[y1][x1]==n:
          dq.append((y1,x1))
        else:
          S.add((y1,x1))
  return S
        
N,M = map(int,input().split())
M += 2
board = [[0]*M]+[[0]+[*map(lambda x:1 if x=="x" else 0,input().strip())]+[0] for i in range(N)]+[[0]*M]
N += 2

result = []; visited = [[0]*M for i in range(N)]
DFS([(0,0)]); result.pop()
print(*result if result else [-1])

BFS+DFS 문제이다.

구현과정이 재미있는 문제였다. 수영장 사장님 [백준 15730번] 수영장 사장님 (Python3) (tistory.com) 문제를 풀 때 떠올렸던 아이디어가 도움이 되었다.

 

풀이를 설명하면,

1. 땅은 1, 바다는 0으로 입력을 받고, 바깥쪽 테두리 부분에 0으로 둘러서 바다를 한줄 더 만든다. (가장 바깥에서부터 하기 위함이다)

2. BFS 함수는 n이 1, d가 8이면 8방향으로 땅을 탐사하고, n이 0, d가 4면 4방향으로 바다를 탐사하는 함수이다. (섬은 대각선으로도 연결되어있다)

3. DFS 함수는 섬 내부의 바다의 좌표를 가지고 있는 ocean set에 대해서 해당 바다좌표 내부의 섬을 모두 찾고, 그 섬들 중 가장 높은 섬의 높이의 +1을 return하는 함수이다.

4. 처음엔 ocean set은 {(0,0)}으로 시작하여 DFS 함수로 각 좌표를 돌면서 내부의 섬을 찾고, 가장 높은 섬의 높이의 +1 값이 곧 현재 섬의 높이가 되므로 그에 해당하는 개수를 +1 해주면 된다.

 

DFS와 BFS를 둘 다 사용해야하는 재미있는 문제였다.

 

 

여담) 내 풀이가 숏코딩 1위, 파이썬 기준 성능 1위가 되었다.