BOJ 백준 파이썬 2636 치즈

boj 5574 일루미네이션이랑 똑같은 문제라 보면 된다.

일루미네이션은 육각형이라 배열 확장이 필요하지만 이 문제는 필요 없다.

결국, 문제는 달라도 푸는 아이디어는 똑같구나라는 생각을 하게 되었으며

문제 풀이 아이디어를 기록하기 위해 블로그를 하게 된 계기인 문제이다.

바깥쪽인 0부터 탐색하며 바깥쪽 0과 접촉한 1은 0으로 변한다는 아이디어를 적용하면 된다.

문제 풀이의 시작이자 끝

 

 

import sys
from collections import deque
from itertools import combinations
 
 
 
def bfs(x,y):
    global ok
    global temp
    q.append((x,y)) ##큐에 원소 집어넣기
 
    while q:
       x,y=q.popleft()
 
       for k in range(4):
           nx=x+dx[k]
           ny=y+dy[k]
 
           if 0<=nx<n and 0<=ny<m:
               if board[nx][ny]==1:
                   board[nx][ny]=0
                   ch[nx][ny]=1
                   ok=1
                   temp+=1
                   #print(999)
 
               else: ## 0일시
                   if ch[nx][ny]==-1:
                       q.append((nx,ny))
                       ch[nx][ny]=1
 
 
if __name__=='__main__':
   # sys.stdin=open("input.txt", "rt")
    
    n,m=map(int,input().split()) ##n=세로(행), m=가로(열)
 
    board=[list(map(int,input().split())) for _ in range(n)] ##입력 받기
 
    
    dx=[0,0,-1,1]
    dy=[1,-1,0,0]
    time=0
 
    q=deque()
    res=0
    while True:
        temp=0
        ch=[[-1]*m for _ in range(n)]
        ch[0][0]=1
        ok=0
        bfs(0,0)
        #print(999)
        time+=1
        if temp!=0:
            res=temp
        if ok==0:
            print(time-1)
            print(res)
            break