[백준/Python] 2638번 - 치즈

문제

백준 2738번 - 치즈

해결 과정

1. bfs함수

• [0][0]부터 큐에 넣고 방문 처리한다.
• while문: 큐가 비어질 때까지 돈다
  • 상하좌우를 확인하며 반복문을 돈다.
  • 범위 안에 있고 방문하지 않았고
    치즈라면 (1보다 크거나 같다면) +1 해준다.
    공기라면 (0이라면) 방문처리를 해주고 큐에 넣어준다.
  • 여기서!!!! 애초에 큐에 공기만 넣기 때문에 공기의 상하좌우만 확인하게 된다.

2. while문: board에 치즈가 없어질 때까지 돈다

• bfs()를 통해 공기에 닿는 치즈를 세어준다.
• 이중포문
  • board가 3이상이라면 녹아없어진거니까 0으로 바꾸고
    시간이 지났으니까 flag=false
  • board가 2라면 치즈인거니까 다시 1로
• flag가 false라면 (시간이 지난 것) t +1
  아니라면 더 이상 녹을 게 없는 것이니까 break하고 t를 리턴

시행착오

• 고민1: 정사각형이 2변 이상 공기와 접촉하는 면인지 어떻게 확인할까?
  -> bfs 를 이용하여 공기의 상하좌우를 확인하며 치즈라면(1보다 크다면) +1 해준다.
  -> 1부터 시작했으니까 3이상이라면 2변 이상 공기와 접촉하는 것
• 고민2: 치즈의 내부에 있는 정사각형인지 어떻게 확인할까?
  -> 큐에 치즈를 넣지않기 때문에 치즈의 상하좌우를 방문하지 않는다.
  -> 그렇게 되면 내부에 있는 정사각형과 치즈는 아예 방문하지 않는다.

풀이

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())
board = [[] for _ in range(n)]

for i in range(n):
  board[i] = list(map(int,sys.stdin.readline().split()))

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs():
  # [0][0]부터 시작
  q = deque([(0,0)])
  # 방문처리
  visited = [[False] * m for _ in range(n)]
  visited[0][0] = True
  
  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 < m:
        # 방문하지 않았고
        if not visited[nx][ny]:
           # 치즈라면 
          if board[nx][ny] >= 1:
            board[nx][ny] += 1          
          # 공기라면 방문 처리하고 큐에 넣어준다.
          else:
            visited[nx][ny] = True
            q.append([nx,ny])
       
t = 0
while True:
  bfs()
  flag = True
  for i in range(n):
    for j in range(m):
      if board[i][j] >= 3:
        board[i][j] = 0
        flag = False
      elif board[i][j] == 2:
        board[i][j] = 1
  if not flag:
    t += 1
  else:
    break

print(t)