[Node.js] 백준 7576 - 토마토

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

라고 합니다.

최소 날짜를 찾자.

문제 구성

창고에 보관된 토마토가 모두 익는 데 걸리는 최소일수 구하기
최소일수는 최단 거리, 따라서 BFS
거리 측정 : BFS의 레벨 증가 = 하루가 증가한다
종료 : 창고에 0 (익지 않은 토마토)가 있다면 -1 출력

정답 코드

const fs = require("fs");
// 백준 채점 환경인 /dev/stdin에서 입력을 읽습니다.
const path = "/dev/stdin"; 

const input = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.replace("\r", "")); // Windows 환경의 \r 제거

// M: 가로(열), N: 세로(행)
const [M, N] = input[0].split(" ").map(Number); 

// 토마토 상자 데이터 (2차원 배열)
const tomatoBox = input.slice(1).map((l) => l.split(" ").map(Number));

// 상하좌우 네 방향 탐색을 위한 배열
const dr = [1, -1, 0, 0];
const dc = [0, 0, -1, 1];

// BFS를 위한 큐 (자바스크립트 배열을 사용, shift() 대신 head 인덱스로 최적화)
const q = []; 
let days = 0; // 최소 날짜

// 1. 초기화: 모든 익은 토마토를 큐에 넣기 (Multi-Source BFS 준비)
for (let r = 0; r < N; r++) {
  for (let c = 0; c < M; c++) {
    if (tomatoBox[r][c] === 1) {
      q.push([r, c, 0]); // [행, 열, 날짜]
    }
  }
}

// 2. BFS 탐색 시작
let head = 0; // 큐의 맨 앞 인덱스 (shift() 대신 사용하여 성능 최적화)
while (q.length > head) {
  const [r, c, currentDay] = q[head++]; // 현재 위치와 날짜를 꺼냅니다.

  days = Math.max(days, currentDay); // 최대 날짜 갱신

  // 4방향 탐색
  for (let i = 0; i < 4; i++) {
    const newR = r + dr[i];
    const newC = c + dc[i];

    // 유효성 검사 (1. 범위 안에 있고, 2. 익지 않은 토마토일 경우 (=== 0))
    if (
      newR >= 0 &&
      newR < N &&
      newC >= 0 &&
      newC < M &&
      tomatoBox[newR][newC] === 0
    ) {
      // 3. 익지 않은 토마토를 익힙니다. (visited 처리 역할)
      tomatoBox[newR][newC] = 1; 
      
      // 큐에 추가하며 날짜를 1 증가시킵니다.
      q.push([newR, newC, currentDay + 1]); 
    }
  }
}

// 3. 결과 확인
let hasZero = false;
for (let r = 0; r < N; r++) {
  for (let c = 0; c < M; c++) {
    if (tomatoBox[r][c] === 0) {
      hasZero = true; // 익지 않은 토마토가 남아있음
      break;
    }
  }
}

// 4. 결과 출력
if (hasZero) {
  console.log(-1); // 모두 익지 못함
} else {
  console.log(days); // 모두 익는 데 걸린 최소 일수
}

주요 로직 설명

head 변수 사용

JS에서 배열의 shift()는 느리다.

따라서 head 인덱스 변수를 사용하여 성능 개선

`tomatoBox`

별도의 visited 배열을 만들지 않고, tomatoBox 배열 자체가 두 가지 역할을 수행.

0: 방문하지 않은(익지 않은) 토마토

1: 방문한(익은) 토마토 또는 처음부터 익은 토마토

-1: 토마토가 없는 칸 (방문 불가)

따라서 tomatoBox[newR][newC] === 0 조건 하나로 방문 여부와 익을 수 있는지 여부를 동시에 검사합니다.

최종 결과

days 변수에 마지막으로 익은 토마토의 거리.
마지막 루프를 통해 0 이 있는지 확인 후 days 혹은 -1 출력

끝!

간만에 bfs하니까 dfs랑 너무 헷갈림…

열심히 공부해서… 열심히 살아야지…

[Node.js] 백준 7576 - 탑 보기

간만에 JS