2638. 치즈

치즈가 먹고싶다.

bfs문제이다. 그래프 탐색문제는 뭔가 코테에서 만나면 아직 어렵게 느껴진다.
다 연습이 부족해서겠지.

이 문제는 바깥 공간과 접촉한 치즈만 녹는다. 이게 힌트이다. 그냥 무지성 bfs (0,0)에서 해주고, 그에 따라서 외부와 접촉한 치즈 (1 ) 을 1씩 증가시킨다. (접촉할 때마다)

즉 3이상이면 2번이상 접촉한거고 다음 반복에서 삭제하면 된다.

import sys
from collections import deque
input = sys.stdin.readline
n,m=map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n)]
dx,dy=[0,0,1,-1],[1,-1,0,0]
ans = 0
while True:
  q = deque()
  visited = [[0 for _ in range(m)] for _ in range(n)]
  visited[0][0] = 1
  q.append([0,0])
  while q:
    x,y = q.popleft()
    for k in range(4):
      nx, ny = x + dx[k], y + dy[k]
      if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
        if board[nx][ny]:
          board[nx][ny] += 1 # 여기서 방문 처리하면 안되요. 왜냐면 또 올수 있어야됨
        else:
          visited[nx][ny] = 1
          q.append([nx, ny])
  flag = 0
  for i in range(n):
    for j in range(m):
      if board[i][j] >= 3:
        board[i][j] = 0
      elif 0 < board[i][j]:
        flag = 1
        board[i][j] = 1
  ans += 1

  if not flag:
    print(ans)
    break

자바스크립트로도 풀었다.

const fs = require("fs")
let input = fs.readFileSync("./dev/stdin").toString().trim().split("\n")
let [a, ...board] = input
let [n, m] = a.split(" ").map((e) => +e)
board = board.map((e) => e.split(" ").map((e) => +e))

let dx = [0, 0, 1, -1],
  dy = [1, -1, 0, 0],
  ans = 0
while (true) {
  let q = []
  q.push([0, 0])
  const visited = Array.from({ length: n }, () =>
    Array.from({ length: m }, () => 0)
  )
  visited[0][0] = 1
  while (q.length) {
    let [x, y] = q.shift()
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i],
        ny = y + dy[i]
      if (nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny] === 0) {
        if (board[nx][ny]) {
          board[nx][ny] += 1
        } else {
          visited[nx][ny] = 1
          q.push([nx, ny])
        }
      }
    }
  }
  let flag = 0
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (board[i][j] >= 3) {
        board[i][j] = 0
      } else if (board[i][j] > 0) {
        flag = 1
        board[i][j] = 1
      }
    }
  }
  ans += 1
  if (!flag) {
    console.log(ans)
    break
  }
}