BOJ-백준7569번 토마토 Javascript Node.js 문제 풀이와 반례

BOJ-백준7569번 토마토 Javascript Node.js 문제 풀이와 반례 입니다.

링크 :https://www.acmicpc.net/problem/7569

7569번: 토마토

 

✅ Node.js 정답 코드 입니다. 더보기 클릭!

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  const [M, N, H] = input
    .shift()
    .split(" ")
    .map((x) => parseInt(x));

  const boxes = [];
  const que = [];
  input = input.map((x) => x.split(" "));

  for (let i = 0; i < H; i++) {
    boxes.push(input.splice(0, N));
  }

  for (let h = 0; h < H; h++) {
    for (let n = 0; n < N; n++) {
      for (let m = 0; m < M; m++) {
        if (boxes[h][n][m] == 1) {
          que.push([h, n, m, 0]);
        }
      }
    }
  }

  /**
   * BFS
   */

  let day = 0;
  let node;
  let idx = 0;
  while (que.length > idx) {
    node = que[idx++];
    bfs(node);
  }
  day = node ? node[node.length - 1] : -1;

  let check = true;
  for (box of boxes) {
    for (tomatos of box) {
      if (tomatos.includes("0")) {
        check = false;
        break;
      }
    }
    if (!check) break;
  }
  check ? console.log(day) : console.log(-1);

  function bfs(p) {
    const z = p[0];
    const x = p[1];
    const y = p[2];
    const day = p[3];
    const dx = [-1, 1, 0, 0, 0, 0];
    const dy = [0, 0, -1, 1, 0, 0];
    const dz = [0, 0, 0, 0, -1, 1];
    for (let i = 0; i < 6; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      const nz = z + dz[i];
      if (nz < 0 || nx < 0 || ny < 0 || nz >= H || nx >= N || ny >= M) continue;
      if (boxes[nz][nx][ny] == -1) continue;
      if (boxes[nz][nx][ny] > 0) continue;
      boxes[nz][nx][ny] = day + 1;
      que.push([nz, nx, ny, day + 1]);
    }
  }

  process.exit();
});

 

📌 해설

BFS 문제이고, 시간제한, 메모리제한을 신경썼어야 했던 문제입니다. 

 

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  const [M, N, H] = input
    .shift()
    .split(" ")
    .map((x) => parseInt(x));

  const boxes = [];
  const que = [];
  input = input.map((x) => x.split(" "));

  for (let i = 0; i < H; i++) {
    boxes.push(input.splice(0, N));
  }

  for (let h = 0; h < H; h++) {
    for (let n = 0; n < N; n++) {
      for (let m = 0; m < M; m++) {
        if (boxes[h][n][m] == 1) {
          que.push([h, n, m, 0]);
        }
      }
    }
  }

1. 입력받기, boxes 그래프 만들기, 큐 초기화 하기

 

입력을 받습니다. 

input.shift() 하여 맨 첫줄은 M,N,H로 저장합니다.

다음 줄 부터 boxes 에 차례로 담아 BFS 를 돌 그래프를 만들어 줍니다. 

 

3중 for 문을 돌면서 boxes 에 가장 처음 담긴 토마토(boxes[h][n][m] == 1) 를 찾아서 큐를 초기화 해줍니다. 

O(H*M*N)

 

2.

  let day = 0;
  let node;
  let idx = 0;
  while (que.length > idx) {
    node = que[idx++];
    bfs(node);
  }
  day = node ? node[node.length - 1] : -1;

while 문으로 큐에서 node 를 idx++ 씩 넘겨가며 bfs를 실행합니다. 

while 문 종료시 day 를 구합니다. 

 

  function bfs(p) {
    const z = p[0];
    const x = p[1];
    const y = p[2];
    const day = p[3];
    const dx = [-1, 1, 0, 0, 0, 0];
    const dy = [0, 0, -1, 1, 0, 0];
    const dz = [0, 0, 0, 0, -1, 1];
    for (let i = 0; i < 6; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      const nz = z + dz[i];
      if (nz < 0 || nx < 0 || ny < 0 || nz >= H || nx >= N || ny >= M) continue;
      if (boxes[nz][nx][ny] == -1) continue;
      if (boxes[nz][nx][ny] > 0) continue;
      boxes[nz][nx][ny] = day + 1;
      que.push([nz, nx, ny, day + 1]);
    }
  }

3. BFS

bfs 함수는 node를 받아 각각 z,x,y,day 에 담습니다.

for문을 통해 큐에 node 를 push 해주기 위해 dx, dy, dz 를 만들어 줍니다. 

for 문 안에서 큐에 담지 않을 node 조건들은 if 분기로 만들어주어 continue 시켜주고 

큐에 담을 node 만 남겨서 push 해줍니다. 

모든 node 를 큐에 담지 않도록 해줍니다.

 

 

 

  let check = true;
  for (box of boxes) {
    for (tomatos of box) {
      if (tomatos.includes("0")) {
        check = false;
        break;
      }
    }
    if (!check) break;
  }
  check ? console.log(day) : console.log(-1);

4. 체크 하고 day 출력

bfs 탐색이 모두 종료되면 boxes 를 마지막으로 검사해줍니다. 

검사가 종료되면 check 에 따라 day 혹은 -1 을 출력합니다.

 

 

 

📌 오답노트

1. 시간초과

while (que.length > 0) {
  const node = que.shift();
  bfs(node);
  day = node.at(-1);
}

while 문 안에서 큐 길이만큼 반복할때 que.shift()를 사용해서 시간초과가 났다. 

shift() 의 시간복잡도는 O(n)이다.

shift() 메서드는 que 에서 원소를 하나 제거하고 연이은 나머지 값들의 위치를 한 칸식 앞으로 당긴다. 

인덱스를 직접 조회하거나, LinkedList 로 Queue를 직접 구현해야한다. 

 

 

 

2. 메모리초과

function bfs(i) {
  const h = i[0];
  const x = i[1];
  const y = i[2];
  const day = i[3];
  if (h < 0 || x < 0 || y < 0 || h >= H || x >= N || y >= M) return false; // 토마토 상자 밖
  if (boxes[h][x][y] == -1) return false; // 토마토가 없음
  if (boxes[h][x][y] > 0) return false; //
  boxes[h][x][y] = day + 1; // 토마토를 익힘
  que.push(
    [h, x + 1, y, boxes[h][x][y]],
    [h, x, y + 1, boxes[h][x][y]],
    [h, x - 1, y, boxes[h][x][y]],
    [h, x, y - 1, boxes[h][x][y]],
    [h + 1, x, y, boxes[h][x][y]],
    [h - 1, x, y, boxes[h][x][y]]
  );
}

일단 그래프 이동 횟수 모두 다 큐에 push 하는 경우 메모리 초과가 날 수 있다. 

필요한 이동만 큐에 push 하고 편리하도록 dx, dy, dz를 만들어주면 좋다.

 

3. 런타임에러

  let day = 0;
  let node;
  let idx = 0;
  while (que.length > idx) {
    node = que[idx++];
    bfs(node);
  }
  day = node[node.length - 1];

while 이 한번도 안 돌 경우 node 가 어떻게 될지 고려를 전혀 안 했다.

 

 

 

 

📌 반례

도움이 되었던(?) 반례

5 3 2
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

output : 0

5 3 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

output : -1

 

::

 

node js 로 풀어본 토마토~