문제 링크

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

문제 설명

• board 주어짐
• 1초마다 외부 공기와 2칸 이상 인접한 칸 사라짐

풀이

• 외부 공기 기준 BFS 반복
• 1초마다 2칸 이상 닿는 좌표 삭제

파이썬 코드

import sys
from collections import deque


def solution():
    read = sys.stdin.readline
    h, w = map(int, read().split())
    board = [list(map(int, read().split())) for _ in range(h)]

    for answer in range(h*w):
        count = [[0] * w for _ in range(h)]
        bfs(h,w,board, count)
        finished = True
        for y in range(h):
            for x in range(w):
                if count[y][x] >= 2:
                    board[y][x] = 0
                    finished = False
        if finished:
            break

    print(answer)


def bfs(h, w, board, count):
    visited = [[0]*w for _ in range(h)]
    dy, dx = [0,0,1,-1],[1,-1,0,0]
    q = deque([[0,0]])
    while q:
        cy, cx = q.popleft()
        for i in range(4):
            ny, nx = cy+dy[i], cx+dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if board[ny][nx] == 0:
                    if not visited[ny][nx]:
                        visited[ny][nx] = 1
                        q.append([ny,nx])
                else:
                    count[ny][nx] += 1


solution()