[백준2638&파이썬] BFS에 구현과 시뮬레이션이 섞인 문제

# 문제

백준 2638 치즈 파이썬 풀이

2638번: 치즈

# 코드

import sys
from collections import deque

def show2D(arr):
  for i in range(len(arr)):
    print(*board[i])

N, M = map(int, sys.stdin.readline().split())
board = list()

dirs = [
  (-1, 0), (0, 1), (1, 0), (0, -1)
  ]

candidaties = list()
for _ in range(N):
  line = list(map(int, sys.stdin.readline().split()))
  board.append(line)

# 치즈의 외곽과 치즈의 외부를 어떻게 구별할 것인가?
  # 내부공기인지의 여부..를 어떻게 알 수 있을까?
  # 해당 좌표에서 4방향을 찍고 내부인지 외부인지 판단해야 할듯
  # 가장자리에는 치즈가 놓이지 않는다. 가장자리는 무조건적으로 외곽이지 않을까? <- 채택
# 동시에 없애야한다.
  # 하나씩 순차적으로 체크하고 없애버리면 영향을 끼치게 된다.
  # 매 탐색 시작시 마다 내 외부를 결정해야하는데.. 이 방법이 맞을까 싶다.

timer = 0
while True:
  # board[0][0]으로 완전탐색 한번 돌려버리고 외곽 외곽은 -1, 내부는 0으로 마킹하자
  dq = deque()
  dq.append((0, 0))  # 첫 가장자리
  end_cnt = 1  # 이게 N*M 되면 종료조건임 ( 모든곳이 다 외곽이라는 뜻 )
  board[0][0] = -1  # 방문표시

  while len(dq) != 0:
    row, col = dq.popleft()
    for dir in dirs:
      next_row = row + dir[0]
      next_col = col + dir[1]
      if 0 <= next_row < N and 0 <= next_col < M:
        if board[next_row][next_col] == 0:  # 치즈 있는 곳이 아니라면
          board[next_row][next_col] = -1  # 방문표시
          dq.append((next_row, next_col))
          end_cnt += 1

  if end_cnt == N * M:  # 모든곳이 다 외곽이기 때문에 종료조건이 된다.
    break

  # 치즈를 녹인다.
  for row in range(N) :
    for col in range(M) :
      if board[row][col] == 1 :
        air_cnt = 0
        for dir in dirs :
          next_row = row + dir[0]
          next_col = col + dir[1]
          if 0<= next_row < N and 0<= next_col < M :
            if board[next_row][next_col] == -1 : # 외부 공기이면
              air_cnt+=1

        if 2<= air_cnt : # 접촉 외부 공기가 2이상일때
          candidaties.append((row,col))

  # 후보군에서 뽑아서 그 자리를 0으로 만든다. ( 치즈를 녹이를걸 후행시키기 위해서 )
  for candidate in candidaties :
    board[candidate[0]][candidate[1]] = 0

  # 다시 원상복귀를 시킨다.
  for row in range(N):
    for col in range(M):
      if board[row][col] == -1:
        board[row][col] = 0
  timer += 1
  candidaties.clear()

print(timer)

# 풀이

• 그래프 탐색을 이용해서 외곽공기와 두곳이상 닿아있는곳을 구하면 된다. 저번에도 유사한 문제를 풀었었는데, 녹을 치즈가 결정되면 그자리에서 녹이면 안된다. 나름의 동시성(?)문제가 생긴다.
• 같은 시간대이지만 반복문으로 그자리에서 녹여버리면 그 옆 치즈가 영향을 받게 된다. 그렇기 때문에 녹일 치즈를 한곳(리스트)에 담아두고, 한번에 그 치즈들을 녹여 board를 업데이트 해줘야한다.
• 위의 내용까지는 아주 쉽다. 그러나 외곽공기와 내부공기를 판별하기 위해서 계속 생각을 해봤다. 
• 왼쪽이나 오른쪽으로 선을 쫙 그어서 다각형의 내외부르 판단해볼까 했었다. ( 이건 아닌거 같아서 안함 )
• 문제를 자세히 읽어보니 가장자리에는 항상 치즈가 놓일 수 없다는 조건이 있었다. 그렇기 때문에 ( 0, 0 )은 항상 외곽공기가 될 것이다. 그러면 그 공기로부터 그래프탐색(BFS)를 돌리면 모든 외곽공기를 알 수 있게 된다.
• 외곽공기를 -1로 마킹하고, 녹일 치즈를 선택하도록 코드를 작성했다. 
• 무엇보다 시간초과 날거 같았는데 안나는게 신기했다.