토마토 1차원(파이썬)

from collections import deque

M,N = map(int, input().split())
tomatos = [list(map(int, input().split())) for _ in range(N)]

# 1: 익은 토마토, 0: 익지않은 토마토, -1: 없음

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

# 1인 곳을 기점으로 탐색 -> 0인경우 1로 변경 -> cnt+=1
# 다시 1인 곳 기점을 재탐색
# 0인 곳이 없을 때까지 반복

cnt = 0 # 토마토가 익을 떄까지의 최소 날짜

# 0인 경우 1로 바꾸는 함수
def makeTomatoGrow(curX, curY):
  for i in range(4):
    nextX = curX + dx[i]
    nextY = curY + dy[i]
  
    if 0 <= nextX < M and 0 <= nextY < N:
      if(tomatos[nextY][nextX]==0):
        tomatos[nextY][nextX] = tomatos[y][x] + 1
        queue.append((nextX, nextY))

# 토마토가 익은 곳 큐에 저장
queue = deque()
for y in range(N):
  for x in range(M):
    if(tomatos[y][x]==1):
      queue.append([x,y])

while(queue):
  x,y = queue.popleft()
  makeTomatoGrow(x, y)

result = 0
for row in tomatos:
  for cell in row:
    if cell == 0:
      print(-1)
      exit()
  
    # cell의 최대값을 찾기
    if(result < cell):
      result = cell

# 1부터 시작했으므로 -1처리해주기
print(result -1)

토마토 3차원(자바스크립트)

잘못된 수식

잘못된 3차원 탐색

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

// tomatos[h][y][x]
// 탐색한 인근 토마토에 대해서 0인경우 1로 변경

queue = [];

function makeTomatoGrow(curX, curY, curH) {
  for (let h = 0; h < 3; h++) {
    nextH = curH + dh[0];
    for (let d = 0; d < 4; d++) {
      nextX = curX + dx[d];
      nextY = curY + dy[d];

      if (0 <= nextX < M && 0 <= nextY < N && 0 <= nextH < H) {
        if (tomatos[nextH][nextY][nextX] === 0) {
          tomatos[nextH][nextY][nextX] = tomatos[curH][curY][curX] + 1;
          queue.push([nextX, nextY, nextH]);
        }
      }
    }
  }
}

3차원 탐색 수정

const dx = [0, 0, 0, 0, 1, -1];
const dy = [0, 0, 1, -1, 0, 0];
const dh = [1, -1, 0, 0, 0, 0];

// tomatos[h][y][x]
// 탐색한 인근 토마토에 대해서 0인경우 1로 변경

queue = [];

function makeTomatoGrow(curX, curY, curH) {
  for (let i = 0; i < 6; i++) {
    const nextX = curX + dx[i];
    const nextY = curY + dy[i];
    const nextH = curH + dh[i];

    if (
      nextX >= 0 &&
      nextX < M &&
      nextY >= 0 &&
      nextY < N &&
      nextH >= 0 &&
      nextH < H
    ) {
      if (tomatos[nextH][nextY][nextX] === 0) {
        tomatos[nextH][nextY][nextX] = tomatos[curH][curY][curX] + 1;
        queue.push([nextX, nextY, nextH]);
      }
    }
  }
}

잘못된 수식

while (queue) {
  [x, y, z] = queue.shift();
  makeTomatoGrow(x, y, z);
}

왜냐면 queue는 항상 true → while(queue.length() > 0) 로 하기

성능 개선

let head = 0;
while (head < queue.length) {
  const [x, y, z] = queue[head++]; // 요소를 당기지 않고 인덱스만 이동 (O(1))
  makeTomatoGrow(x, y, z);
}

최종코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const [M, N, H] = input[0].split(" ").map(Number);

const tomatos = [];
let currentLine = 1;
for (let h = 0; h < H; h++) {
  let board = [];
  for (let n = 0; n < N; n++) {
    const rows = input[currentLine++].split(" ").map(Number);
    board.push(rows);
  }
  tomatos.push(board);
}

//console.log(tomatos);

const dx = [0, 0, 0, 0, 1, -1];
const dy = [0, 0, 1, -1, 0, 0];
const dh = [1, -1, 0, 0, 0, 0];

// tomatos[h][y][x]
// 탐색한 인근 토마토에 대해서 0인경우 1로 변경

queue = [];

function makeTomatoGrow(curX, curY, curH) {
  for (let i = 0; i < 6; i++) {
    const nextX = curX + dx[i];
    const nextY = curY + dy[i];
    const nextH = curH + dh[i];

    if (
      nextX >= 0 &&
      nextX < M &&
      nextY >= 0 &&
      nextY < N &&
      nextH >= 0 &&
      nextH < H
    ) {
      if (tomatos[nextH][nextY][nextX] === 0) {
        tomatos[nextH][nextY][nextX] = tomatos[curH][curY][curX] + 1;
        queue.push([nextX, nextY, nextH]);
      }
    }
  }
}

for (let h = 0; h < H; h++) {
  for (let n = 0; n < N; n++) {
    for (let m = 0; m < M; m++) {
      if (tomatos[h][n][m] === 1) {
        queue.push([m, n, h]);
      }
    }
  }
}

let head = 0;
while (queue.length > head) {
  const [x, y, z] = queue[head++]; // shift() 대신 인덱스로 접근
  makeTomatoGrow(x, y, z);
}

let result = 0;

for (let h = 0; h < H; h++) {
  for (let n = 0; n < N; n++) {
    for (let m = 0; m < M; m++) {
      if (tomatos[h][n][m] === 0) {
        console.log(-1);
        process.exit();
      }
      if (tomatos[h][n][m] > result) {
        result = tomatos[h][n][m];
      }
    }
  }
}

console.log(result - 1);