[백준 - Node.js] 토마토 7576번

문제

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

7576번: 토마토

---

문제 풀이

키포인트

1. 시간제한을 해결하기 위한 큐 구현

2. 익은 토마토의 전염은 동시에 진행되어야 한다.

3. 전부 익지 못하는 경우를 어떻게 체크할 것인가?

 

// 큐 구현
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  enqueue(val) {
    const newNode = new Node(val);
    if (this.size === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    this.size++;
  }

  dequeue() {
    const oldFirst = this.first;
    if (this.size === 0) return undefined;
    if (this.size === 1) {
      this.first = null;
      this.last = null;
    } else {
      this.first = oldFirst.next;
    }
    this.size--;
    return oldFirst;
  }
}

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

let input = [];
let N = 0;
let M = 0;
let count = 0;

rl.on('line', function (line) {
  if (!count) {
    const [m, n] = line.split(' ').map(Number);
    N = n;
    M = m;
  } else {
    input.push(line.split(' ').map(Number));
  }
  count++;
}).on('close', function () {
  solution(input);
  process.exit();
});

const solution = input => {
  // 기본세팅
  const visited = [];
  const queue = new Queue();
  const dy = [-1, 0, 1, 0];
  const dx = [0, 1, 0, -1];
  // 최소일수
  let minDay = 1;
  // 0이 포함되는지 여부 확인용
  let check = true;

  // 방문배열 생성
  for (let i = 0; i < N; i++) {
    visited[i] = new Array(M).fill(0);
  }

  // bfs
  const bfs = () => {
    while (queue.size) {
      const [y, x] = queue.dequeue().val;

      // 4방향 순회
      for (let i = 0; i < 4; i++) {
        const ny = y + dy[i];
        const nx = x + dx[i];
        // 그래프의 범위안에 들어온다면 실행
        if (ny >= 0 && nx >= 0 && ny < N && nx < M) {
          // 방문하지 않았고 값이 0 인경우에 (=익혀야할 토마토)
          if (!visited[ny][nx] && input[ny][nx] === 0) {
            // 일수 계산
            visited[ny][nx] = visited[y][x] + 1;
            queue.enqueue([ny, nx]);
            // minday 갱신
            if (minDay < visited[ny][nx]) minDay = visited[ny][nx];
          }
        }
      }
    }
  };
  // 실행
  // 익은 토마토가 여러개인 경우에 동시에 실행되어야 하므로
  // bfs시작전에 queue에 1인 경우를 모두 넣어준다
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      // 방문X인동시에 익은토마토인경우에
      if (!visited[i][j] && input[i][j] === 1) {
        //  방문체크
        // 익지않은 토마토 0을 체크하기 위하여 1부터 시작 (나중에 -1 빼줘야함)
        visited[i][j] = 1;
        queue.enqueue([i, j]);
        // 따로 토마토가 없는 경우는 -1로 미리 체크해준다
      } else if (input[i][j] === -1) {
        visited[i][j] = -1;
      }
    }
  }

  bfs();

  // 출력
  // visited 그래프에서 0인 경우란 방문하지 않은경우이므로
  // check변수를 false 전환
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (visited[i][j] === 0) {
        check = false;
      }
    }
  }
  // check가 true인경우에는 최소일수에서 1 빼고
  // false인경우에는 -1 출력
  console.log(check ? minDay - 1 : -1);
};