[백준] 7576. 토마토 (자바스크립트/node.js/javascript/BFS)

 

위의 예제들은 쉽게 답이 나올 수 있다.

그러나 어려운 반례를 찾아보았는데

 

예제 입력 6

30 19
0 -1 0 0 1 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 -1
-1 0 0 0 0 0 -1 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 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 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 -1
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
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
0 -1 0 0 -1 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 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 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 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 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 1 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 1 0 0 0 0 0 1 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 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 1 0 0

 

예제 출력 6

13

 

예제 입력 7

6 4 
0 0 0 0 0 0 
0 0 1 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 1 

 

예제 출력 7

4

 

백준에서 주어진 예제 1 ~ 예제 5 까지는 잘 보면 익은 토마토가 구석에만 있기 때문에 익은 토마토끼리 겹칠 일(?)이 없다. 그래서 처음엔 위의 예제들만 돌려보고 답이 잘 나와서 제출해보았더니 2%에서 틀렸습니다 라고 나왔다.

그래서 다른 반례를 찾아보았고, 예제 6 같은 경우에 실제로 머리로 생각하기에는 너무 복잡하고 크기 때문에 나는 우선은 예제 7을 가지고 공책에 직접 풀어보면서 했다.

예제 7의 경우 위와 같이 나오면 된다. 

내가 이 문제를 풀 수 있었던 결정적인 포인트는 바로, 이미 익은 토마토가 여러개라면 토마토의 전염(?)은 동시에 된다는 것이다.

위의 사진을 참고하면 0일차에는 (1,2) (3,5)에만 토마토가 있었으나

하루가 지난 1일차에는 처음 토마토가 있었던 (1,2)와 (3,5)에서 동시에 토마토가 익었다.

이것을 유념하여 푸는 것이 중요하다.

 

let fs = require("fs");
let tomato = fs.readFileSync("예제.txt").toString().split("\n");
tomato = tomato.map((element) => element.trim().split(" "));
const row = Number(tomato[0][1]); // 세로: 행
const column = Number(tomato[0][0]); // 가로: 열
tomato.shift();

const ripeTomato = Array.from(new Array(row), () => new Array(column).fill(0));
const moveRow = [0, 0, 1, -1];
const moveCol = [1, -1, 0, 0];
let answer;

const rangeCheck = (r, c) => {
  if (r >= 0 && r < row && c >= 0 && c < column) {
    return true;
  }
  return false;
};

const BFS = (queue) => {
  let number = 0;
  while (number !== queue.length) {
    const currentRow = queue[number][0];
    const currentCol = queue[number][1];
    for (let n = 0; n < 4; n++) {
      const nextRow = currentRow + moveRow[n];
      const nextCol = currentCol + moveCol[n];
      if (
        rangeCheck(nextRow, nextCol) &&
        !ripeTomato[nextRow][nextCol] &&
        Number(tomato[nextRow][nextCol]) === 0
      ) {
        queue.push([nextRow, nextCol]);
        ripeTomato[nextRow][nextCol] = ripeTomato[currentRow][currentCol] + 1;
        answer = ripeTomato[nextRow][nextCol];
      }
    }
    number++;
  }
  answer = answer - 1;
};

const queue = [];
let zero = false;

for (let r = 0; r < row; r++) {
  for (let c = 0; c < column; c++) {
    if (Number(tomato[r][c]) === 1) {
      queue.push([Number(r), Number(c)]);
      ripeTomato[Number(r)][Number(c)] = 1;
    } else if (Number(tomato[r][c]) === -1) {
      ripeTomato[Number(r)][Number(c)] = -1;
    } else if (Number(tomato[r][c]) === 0) {
      zero = true;
    }
  }
}

if (!zero) {
  answer = 0;
} else {
  BFS(queue);
  for (let i = 0; i < ripeTomato.length; i++) {
    if (ripeTomato[i].includes(0)) {
      answer = -1;
      break;
    }
  }
}

console.log(ripeTomato);
console.log(answer);

 

 나는 visited 대신 ripeTomato라는 배열을 만들었다. 방문을 했는지 안했는지보다 토마토가 어떤 순서로 익게 되었는지 담는 것이 더 이해하기 쉽기 때문이다.

처음에 주어진 토마토 인풋을 반복문으로 돌면서 토마토가 존재한다면 큐에 넣는다. 그리고 익은 토마토(ripeTomato) 배열에 1을 넣어준다. (처음부터 익어있던 토마토니까 1이라고 표시함)

그리고 BFS 함수를 만들었고, 큐에서 하나씩 꺼내어 (원래 BFS에서는 shift를 쓰지만, 나는 시간초과가 날 것을 우려하여 배열의 인덱스로 접근하였다) 동서남북 중에서,  1) 그 곳이 이동가능한 곳인지 범위를 체크하고 2) 익은 토마토 배열에 아직 들어가 있지 않고  3) 원래 안익은 토마토라면 큐에다 넣는다. 

큐에 넣은 다음에는 현재 while문에서 돌고 있는 토마토의 ripeTomato 값보다 1 큰 값을 넣어주면 같은 날에 익는 토마토를 알 수 있다.

 

만약 처음부터 다 익어져있다면 0을 출력해야 한다.

-> 이 경우 zero 변수를 넣어서 맨 처음에 반복문을 돌며 인풋을 받을 때 하나라도 안익은 토마토가 있다면  zero를 false로 변경하면 된다.

모든 토마토를 익힐 수 없다면 -1을 출력해야 한다.

-> 이 경우 BFS를 모두 실행한 다음에 하나라도 안 익은 토마토(0)가 나오면 -1을 출력하도록 하면 된다.

위의 두가지 경우가 모두 아니라면 모든 토마토가 익게된 날짜를 출력해야 하는데,

나는 문제를 풀며 토마토가 어떤 순서로 익는지 편하게 보기 위해서 1 다음에 2를 넣도록 했기 때문에, 가장 마지막 날짜에서 -1을 빼고 출력하면 그게 답이 된다.