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

2025. 2. 22. 01:38·PS

 

 


 

문제

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을 빼서 출력합니다.

 


 

저작자표시 비영리 동일조건 (새창열림)

'PS' 카테고리의 다른 글

[백준] 2108번: 통계학 (JavaScript)  (0) 2025.02.23
[백준] 1213번: 팰린드롬 만들기 (JavaScript)  (0) 2025.02.22
[백준] 11053번: 가장 긴 증가하는 부분 수열 (JavaScript)  (0) 2025.02.21
[백준] 1062번: 연결 요수의 개수 (JavaScript)  (0) 2025.02.20
[백준] 13904번: 과제 (JavaScript)  (0) 2025.02.20
'PS' 카테고리의 다른 글
  • [백준] 2108번: 통계학 (JavaScript)
  • [백준] 1213번: 팰린드롬 만들기 (JavaScript)
  • [백준] 11053번: 가장 긴 증가하는 부분 수열 (JavaScript)
  • [백준] 1062번: 연결 요수의 개수 (JavaScript)
abyss-s
abyss-s
프론트엔드 개발합니다!
  • abyss-s
    abyss-s의 블로그입니다.
    abyss-s
  • 전체
    오늘
    어제
    • 분류 전체보기 (192)
      • Web (16)
        • JavaScript (6)
        • TypeScript (1)
        • React (5)
        • Vue (0)
        • Storybook (1)
        • Next.js (1)
      • Backend & Infra (8)
        • Database (3)
        • Node.js (2)
        • SpringBoot (1)
      • PS (71)
      • CS (30)
        • OS (13)
        • Structure & Algorithm (5)
        • Network (10)
        • 정보처리기사 (2)
      • Language (18)
        • OOP (1)
        • JAVA (13)
        • C++ (4)
      • Activities (16)
        • 멋쟁이 사자처럼 (2)
        • OSSCA (3)
        • LG U+ URECA (5)
        • Project (2)
        • Conference (1)
      • IT (3)
      • AI (0)
      • Git & Github (5)
      • Notion (1)
      • Statistics (11)
      • Book (5)
      • Diary (1)
      • Game (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • 깃허브
    • 백준
    • 트위터
  • 공지사항

    • abyss-s의 티스토리에 오신 것을 환영합니다.
  • 인기 글

  • 태그

    OS
    통계학
    생활코딩
    DP
    그리디
    자바기반응용프로그래밍
    BFS
    자바스크립트
    운영체제
    github
    네트워크
    C++
    Java
    BAEKJOON
    React
    Python
    파이썬
    JavaScript
    백준
    코드트리
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
abyss-s
[백준] 7576번: 토마토 (JavaScript)
상단으로

티스토리툴바