[백준] 7576번 토마토 - JavaScript(NodeJS)

문제

 

7576번: 토마토

 

풀이

토마토가 익기 위한 조건은 인접한 익은 토마토가 있고 하루가 지났을 때이다.

 

처음에 상자에서 익은 토마토들의 좌표를 파악해야 한다.

익은 토마토들의 좌표를 기준으로 하루마다 동서남북으로 전염(?)된다고 생각하자.

모든 행렬의 좌표를 조회할 필요는 없다.

 

BFS를 사용해보자.

 

중요한 점은 하루마다 전날 추가된 익은 토마토들의 주변을 모두 탐색해야 한다.

전날에 익은 토마토가 3개가 있다면, 그 3개의 주변을 모두 탐색한다.

 

탈출 조건으로는 더이상 다른 토마토를 익게할 수 없다면, 루프를 끝내면 된다.
다른 토마토가 있다면 하루를 증가시키고, 토마토를 탐색하러 가자.

변수 소개

box : 토마토 박스 정보가 담긴 행렬
M, N : N행 M열
day : 날짜
dx, dy : 동서남북 조회를 위한 좌표 이동 값
iter : 전날 익은 토마토의 개수(이 개수만큼 동서남북 조회를 반복)
change : 전날 익은 토마토에 의해 오늘 다른 토마토가 익었는지 여부를 판단할 변수
queue : 전날 익은 토마토가 담긴 배열

 

const sol = (input) => {
  const [M, N] = input[0].split(" ").map((v) => +v);
  const box = [];
  const queue = [];
  for (let i = 1; i <= N; i++) {
    const arr = input[i].split(" ").map((v) => +v);
    box.push(arr); // 각 행의 토마토 정보 배열를 박스 행렬에 담는다.
    let idx = -1;
    while (true) {    // 박스에서 익은 토마토가 있다면 좌표를 queue에 넣어준다.
      idx = arr.indexOf(1, idx + 1);
      if (idx === -1) break;
      queue.push([i - 1, idx]);
    }
  }

  let day = 0;
  function bfs() {
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    while (queue.length) {
      let iter = queue.length; // 전날에 익은 토마토의 개수
      let change = 0;
      for (let i = 0; i < iter; i++) { // 전날에 익은 모든 토마토의 동서남북 좌표를 조회한다.
        const [x, y] = queue.shift();
        for (let i = 0; i < 4; i++) {
          const [nx, ny] = [x + dx[i], y + dy[i]];
          if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
          if (!box[nx][ny]) {
            change = 1; // 전날 익은 토마토가 오늘 다른 토마토를 익게 했다면 change 변수 증가
            box[nx][ny] = day + 1;
            queue.push([nx, ny]);
          }
        }
      }
      if (!change) break; // change 변수가 변하지 않았다면, 더이상 익을 수 있는 토마토가 없으므로 탈출
      day++; // change 변수가 변했다면, 다음날 익힐 토마토를 조회해야 하므로 하루 증가.
    }
  }
  bfs();

  for (let i = 0; i < N; i++) { 
    if (boxd[i].includes(0)) { // 상자에 익지 않은 토마토가 있으면 -1 출력
      return -1;
    }
  }
  return day; // 모든 토마토가 익었다면, 모두 익기까지 걸린 날짜 출력.
};

// 백준에서 입력을 받기 위한 함수
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });

다음과 같은 방법으로 조회했다.

 

크롬 콘솔에서는 문제 없이 동작하였으나, 정답 검증에서 시간초과 이슈가 있었다.

무슨 문제일지 생각하다가, shift 메서드로 인한 시간초과 가능성을 생각했다.

 

Arrray.prototype.shift

Array.prototype.shift 는 배열의 맨 처음(0번 인덱스) 값을 내보내는 메서드인데,
문제는 이게 시간복잡도가 O(n)이다.

 

배열에서 0번 인덱스의 값을 빼버린다면, 1번 인덱스를 0번으로, 2번 인덱스를 1번으로 ... n번 인덱스를 n-1로 옮겨줘야 하기 때문

 

shift 메서드 없이 수행해보면 아마 시간초과 이슈에서 벗어날 듯 했다.

 

그냥 배열에서 값을 내보내지 말고, 배열에 값을 계속 쌓으면서 배열 인덱스를 늘리면서 조회해보자.

 

코드

2가지 변수를 추가하고, queue.shift => queue[idx] 조회로 방법을 바꿔본다.
이외의 변동 사항은 없다.

const sol = (input) => {
  const [M, N] = input[0].split(" ").map((v) => +v);
  const box = [];
  const queue = [];
  for (let i = 1; i <= N; i++) {
    const arr = input[i].split(" ").map((v) => +v);
    box.push(arr);
    let idx = -1;
    while (true) {
      idx = arr.indexOf(1, idx + 1);
      if (idx === -1) break;
      queue.push([i - 1, idx]);
    }
  }

  let day = 0;
  function bfs() {
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    let prevIdx = 0;    // 조회를 시작할 인덱스
    while (true) {
      const curIdx = queue.length; // queue 크기는 계속 늘어나므로 queue.length-1 까지 조회한다.
      let change = 0;
      for (let i = prevIdx; i < curIdx; i++) {
        const [x, y] = queue[i];
        for (let i = 0; i < 4; i++) {
          const [nx, ny] = [x + dx[i], y + dy[i]];
          if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
          if (!box[nx][ny]) {
            change = 1;
            box[nx][ny] = day + 1;
            queue.push([nx, ny]);
          }
        }
      }
      if (!change) break;
      day++;
      prevIdx = curIdx; // curIdx-1까지 조회가 끝나면, curIdx부터 다시 조회를 시작한다.
    }
  }
  bfs();

  for (let i = 0; i < N; i++) {
    if (box[i].includes(0)) {
      return -1;
    }
  }
  return day;
};

const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });

 

queue 크기가 늘어남에 따라,
prevIdx, curIdx가 (0,2) => (2,5) => (5,8) => .... 와 같이 인덱스가 커지면서 순회한다.

 

뭔가 찝찝하긴 하지만,, 인덱스 조회로 코드를 실행해보면 시간초과 이슈 없이 문제를 해결할 수 있었다.