[백준 / BOJ] 7576번 토마토 ( Node js / Javascript )

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

 

 

---

문제 풀이

토마토는 BFS의 대표 문제들 중 하나입니다. 만약 BFS 혹은 그래프 탐색 자체에 대한 지식이 부족하다면 아래 링크를 참고하시길 바랍니다.

너비 우선 탐색(BFS)와 깊이 우선 탐색(DFS)

 

본인이 떠올린 문제 해결 방안은 다음과 같습니다.

1. 배열을 순회하며 1의 위치들 즉, 시작점들을 큐에 넣어준다.
2. 시작점들이 담겨있는 큐로 BFS를 실행한다.
    방문 정점의 다음 방문 정점들은 해당 정점의 상, 하, 좌, 우에 위치한 인접 노드들이 된다.
3. 모든 시작 노드들의 [상, 하, 좌, 우] 인접 노드들을 큐에 넣고 나면, Day를 1 증가시킨다.

 

여기서 주목해야 될 점은 Day가 증가하는 시점이다. 예를 들면 시작 정점이 [1,1] 과 [3,3]이 존재한다고 가정하자. 그렇다면 다음 Day + 2에서 방문하게 될 정점들은 [1,0], [1,2], [0,1], [2,1] 과 [3,2], [3,4], [2,3], [4,2]가 된다.

[1,0], [1,2], [0,1], [2,1] 를 큐에 넣은 시점에 Day 를 1증가시키는 것이 아닌, 해당 시점의 큐에 존재하는 모든 정점들의 다음 정점들을 큐에 넣은 다음에야 Day를 1증가시키는 것이 중요하다.

 

---

이제 절차별로 코드에서 직접 살펴보겠습니다.

 

1. 배열을 순회하며 1의 위치들 즉, 시작점들을 찾고, 큐에 넣어줍니다.

box.forEach((row, i) =>
  row.forEach((tomato, j) => {
    if (tomato === 1) queue.push([i, j]);
  })
);

---

   2. 시작점들이 담겨있는 큐로 BFS를 실행합니다.

const directions = [
  [1, 0],  //상
  [-1, 0], //하
  [0, 1],  //우
  [0, -1], //좌
];

while (queue.length > 0) {
  nextQueue = [];
  queue.forEach(([x, y]) => {
    directions.forEach(([dx, dy]) => {
      const nx = x + dx,   // 다음 방문 정점은 현재 정점의 상 || 하 || 좌 || 우
        ny = y + dy;
      if (nx >= 0 && nx < N && ny >= 0 && ny < M && box[nx][ny] === 0) {
        box[nx][ny] = 1;
        nextQueue.push([nx, ny]);
      }
    });
  });
  queue = nextQueue;
}

---

3. 모든 시작 노드들의 [상, 하, 좌, 우] 인접 노드들을 큐에 넣고 나면, Day를 1 증가시킵니다.

while (queue.length > 0) {
  nextQueue = [];
  queue.forEach(([x, y]) => {
    directions.forEach(([dx, dy]) => {
      const nx = x + dx,
        ny = y + dy;
      if (nx >= 0 && nx < N && ny >= 0 && ny < M && box[nx][ny] === 0) {
        box[nx][ny] = 1;
        nextQueue.push([nx, ny]);
      }
    });
  });
  queue = nextQueue;
  if (queue.length > 0) days++;  // <---------- 마지막 탐색이 끝난 시점에는 day를 증가시키지 않음
}

 

---

마지막으로 전체 코드와 함께 포스팅을 마치겠습니다.

//토마토 (2차원)
const fs = require('fs');

let [[M, N], ...box] = fs
  .readFileSync('../input.txt')
  .toString()
  .trim()
  .split('\n')
  .map((row) => row.split(' ').map(Number));

const directions = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];

let queue = [],
  nextQueue;
let days = 0;

// 초기 익은 토마토 위치 찾기
box.forEach((row, i) =>
  row.forEach((tomato, j) => {
    if (tomato === 1) queue.push([i, j]);
  })
);

// BFS 실행
while (queue.length > 0) {
  nextQueue = [];
  queue.forEach(([x, y]) => {
    directions.forEach(([dx, dy]) => {
      const nx = x + dx,
        ny = y + dy;
      if (nx >= 0 && nx < N && ny >= 0 && ny < M && box[nx][ny] === 0) {
        box[nx][ny] = 1;
        nextQueue.push([nx, ny]);
      }
    });
  });
  queue = nextQueue;
  if (queue.length > 0) days++;
}

// 모든 토마토가 익었는지 확인
const isAllRipe = box.every((row) => row.every((tomato) => tomato !== 0));

console.log(isAllRipe ? days : -1);