[백준 | node.js] 7576번: 토마토 BFS 풀이

백준 7576번 토마토 문제 링크

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

---

문제 정리

- 토마토가 모두 익을 때까지의 최소 날짜를 구하는 문제

- 1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토가 들어있지 않은 칸

- 익은 토마토는 상하좌우 방향으로 인접한 토마토를 하루에 하나씩 익게 한다.

문제 출력

- 저장될 때부터 모든 토마토가 익어있는 상태라면 0

- 토마토가 모두 익지는 못하는 상황이면 -1

- 그 외의 경우 걸리는 최소 일수

문제 접근

0. 문제 유형 파악하기

익은 토마토가 인접한 토마토를 하나씩 익게하고 전체를 모두 익게 하는데 걸리는 최소 일수를 요구했으므로 BFS 로 풀이한다.

시작점이 여러 개(=익은 토마토들의 위치)라는 점이 특징이다.

 

1. 초기 설정

- 상하좌우 방향 벡터를 설정한다.

- visited 배열 : 익은 날짜를 기록하는 곳

- queue : 익은 토마토의 위치를 저장하는 곳

 

2. 토마토 상태 파악하기

- 익은 토마토는 익은 토마토의 위치를 queue에 저장한다. (시작점이 여러개)

- 빈 공간은 visitied에 -1로 표시한다.

 

3. BFS 로 토마토 익히기

- queue에서 꺼낸 토마토의 위치 4방향을 탐색한다.

- 새로운 위치 && 안 익은 토마토 라면 익히고, visited, queue 업데이트한다.

 

4. visited 최댓값 return

- 안 익은 토마토가 있으면 -1

---

첫 번째 코드 : 시간 초과

function solution(m, n, graph) {
  // 기초 세팅 (방향(상하좌우), 방문처리(날짜+1), 큐(익어있는 토마토들의 위치))
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  let visited = Array.from({ length: n }, () => Array(m).fill(0)); // 날짜를 처리하는 곳
  let queue = []; // 익은 토마토들의 위치 담는 곳

  for (let i = 0; i < graph.length; i++) {
    for (let j = 0; j < graph[0].length; j++) {
      if (graph[i][j] === 1) {
        // 익은 토마토가 있는 경우
        queue.push([i, j]);
        visited[i][j] = 0;
      }
      if (graph[i][j] === -1) {
        // 토마토 없는 경우
        visited[i][j] = -1;
      }
    }
  }

  // bfs 탐색 : 1(익은 토마토) 탐색하기 - 익은 토마토가 여러개라서 시작점이 여러개.
  // 유효성 검사 (토마토가 없다.)
  while (queue.length > 0) {
    let [x, y] = queue.shift();

    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (graph[nx][ny] === 0 && visited[nx][ny] === 0) {
        visited[nx][ny] = visited[x][y] + 1;
        queue.push([nx, ny]); // 안익은 토마토가 익었으니까 당연히 push!
      }
    }
  }

  let maxDay = 0;
  // 최댓값만 업데이트하는게 아닌, 0이 하나라도 있으면 -1을 반환해야한다. (다 익지 않았으므로)
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (visited[i][j] === 0 && graph[i][j] === 0) {
        return -1;
      }
      if (maxDay < visited[i][j]) {
        maxDay = visited[i][j];
      }
    }
  }
  return maxDay; // visited의 최댓값 반환
}

console.log(
  solution(6, 4, [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1],
  ])
); // 8

console.log(
  solution(6, 4, [
    [0, -1, 0, 0, 0, 0],
    [-1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1],
  ])
); // -1

console.log(
  solution(5, 5, [
    [-1, 1, 0, 0, 0],
    [0, -1, -1, -1, 0],
    [0, -1, -1, -1, 0],
    [0, -1, -1, -1, 0],
    [0, 0, 0, 0, 0, 0],
  ])
); // 14

문제 원인

queue.shift() 연산은 O(n)의 시간 복잡도를 가지고, 큐의 크기가 커지면 성능이 저하된다.

예를 들어, 1000x1000 크기의 토마토 상자에서 최악의 경우: 백만 개의 칸을 모두 방문할 수도 있다.

 

해결하기

1. queue.shift() 대신 인덱스를 사용한다.

========== 추가적으로 성능 최적화 ===========

2. 날짜 정보를 큐에 함께 저장 [x, y, day] 한다.

3. visited 배열은 방문 여부만 체크한다.

---

최종 코드

function solution1(m, n, graph) {
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  let visited = Array.from({ length: n }, () => Array(m).fill(0)); // 방문처리만!
  let queue = [];
  let maxDay = 0;

  for (let i = 0; i < graph.length; i++) {
    for (let j = 0; j < graph[0].length; j++) {
      if (graph[i][j] === 1) {
        queue.push([i, j, 0]);
      } else if (graph[i][j] === -1) {
        visited[i][j] = -1;
      }
    }
  }
  
  let idx = 0;
  while (idx < queue.length) {
    let [x, y, day] = queue[idx++];
    maxDay = Math.max(maxDay, day);

    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (graph[nx][ny] === 0 && visited[nx][ny] === 0) {
        visited[nx][ny] = 1;
        queue.push([nx, ny, day + 1]);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (graph[i][j] === 0 && !visited[i][j]) return -1;
    }
  }
  return maxDay;
}