[백준] 7576번: 토마토 (JavaScript)

 

 

---

 

문제

https://www.acmicpc.net/problem/7576

 

 

개념

• 그래프 탐색
• BFS

 

구현 코드(JavaScript)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [m, n] = input[0].split(' ').map(Number);
const tomatoes = input.slice(1).map((row) => row.split(' ').map(Number));
let q = [];
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
let day = 0;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (tomatoes[i][j] === 1) {
      q.push([i, j]);
    }
  }
}

let front = 0;

while (front < q.length) {
  const size = q.length - front; // 현재 day에 익힐 수 있는 토마토 개수

  for (let i = 0; i < size; i++) {
    const [x, y] = q[front++];

    for (let j = 0; j < 4; j++) {
      const nx = x + dx[j];
      const ny = y + dy[j];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (tomatoes[nx][ny] !== 0) continue;
      tomatoes[nx][ny] = 1; // 익힘 처리
      q.push([nx, ny]);
    }
  }
  day++;
}

// 모든 토마토가 익었는지 확인
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (tomatoes[i][j] === 0) {
      console.log(-1);
      return;
    }
  }
}

console.log(day - 1);

 

 

 

 

코드 설명

문제 분석

토마토는 하루가 지나면 익은 토마토의 상하좌우에 있는 익지 않은 토마토를 익게 만든다는 조건이 있습니다.

주어진 토마토가 모두 익는 최소 일수를 구하는 문제이므로, BFS를 이용할 수 있습니다.

 

왜 BFS?

큐에서 꺼낸 토마토는 상하좌우 네 방향으로 퍼져 나가며, 익지 않은 토마토를 익히기 때문에 너비 우선 탐색을 사용합니다.

 

• 한 번 익은 토마토는 다시 바뀌지 않음 → 같은 위치를 다시 탐색할 필요 없음
• 모든 방향(상하좌우)으로 한 번씩만 탐색 → 불필요한 중복 계산 없음
• 탐색이 끝난 후 가장 늦게 익은 토마토가 걸린 일수가 최종 출력해야 하는 답입니다.

 

 

BFS를 활용한 토마토 익히기 과정

(1) 초기 큐(Queue) 설정

BFS에서는 시작점을 큐에 먼저 넣고 탐색을 진행합니다.
이 문제에서는 이미 익은 토마토(1인 토마토들)를 모두 큐에 넣고 시작합니다.

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (tomatoes[i][j] === 1) {
      q.push([i, j]);
    }
  }
}

 

 

(2) BFS 진행 (익히기 과정)

1. 큐에서 익은 토마토를 하나씩 꺼내고, 사방 탐색합니다.
2. 인접한 칸에 아직 익지 않은 토마토(값이 0인 경우) 가 있다면 익힘 처리(값을 1로 변경)합니다
3. 익은 토마토를 새로운 큐에 추가하여 다음 날에 탐색할 수 있도록 함
4. 이 과정을 큐가 빌 때까지 반복합니다.

let front = 0;
while (front < q.length) {
  const size = q.length - front;  // 현재 day에서 익힐 수 있는 토마토 개수
  for (let i = 0; i < size; i++) {
    const [x, y] = q[front++];  // 현재 익은 토마토의 좌표

    for (let j = 0; j < 4; j++) {  // 상하좌우 네 방향 탐색
      const nx = x + dx[j];
      const ny = y + dy[j];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 벗어나면 스킵
      if (tomatoes[nx][ny] !== 0) continue; // 이미 익었거나 빈 칸(-1)이면 스킵
      tomatoes[nx][ny] = 1; // 익힘 처리
      q.push([nx, ny]); // 큐에 추가하여 다음 날 탐색할 수 있도록 함
    }
  }
  day++;  // 하루 증가
}

 

큐에서 꺼낸 익은 토마토가 네 방향으로 퍼지면서 새롭게 익는 토마토들을 다음 날 익힐 목록으로 추가하는 구조입니다.

 

3. BFS 탐색 종료 후 최종 검사

BFS가 끝난 후에도 익지 않은 토마토(0)가 남아 있다면 -1을 출력합니다.

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (tomatoes[i][j] === 0) {
      console.log(-1);
      return;
    }
  }
}
console.log(day - 1);  // BFS에서 하루씩 증가했으므로 마지막에 1 빼줌

 

BFS를 끝까지 돌렸음에도 0이 남아 있다면, 익지 못하는 토마토가 존재하는 것이므로 -1을 출력합니다.

마지막날에 day++가 불필요하게 한 번 더 발생하므로 최종 출력에서는 1을 빼서 출력합니다.

 

---