[백준] 7576번 : 토마토 (골드Ⅴ) by node.js

▷ 문제 : 7576번 - 토마토

7576번: 토마토

▷ 해결 날짜 : 2022.04.07
▷ 소요 시간 : 1시간 30분
▷ 풀이 과정 :

처음으로 풀어보는 골드 난이도다.

문제를 보면 상자의 크기가 주어지고 토마토의 위치가 주어지는데 1의 위치부터 상하좌우 번져가면서 토마토를 익혀 총 몇일이 걸리는지 확인하는 문제이다.

 

결국 다른 문제와 마찬가지로 1부터 시작해서 전체를 쭉 탐색하면 되는것인데, 시간 초과에서 걸려버렸다.

그래서 일단 시간초과에 걸릴만한 녀석들과 로직을 정리를 해주었다.

 

처음에는 로직을 한번돌때마다 카운팅을 해주는 방식으로 진행했는데, 그 반대로 초기값에서 빼주는 형식으로 로직을 변경하였고 (count-- 부분), queue에 넣어둘때 어차피 하루씩 걸리니까 날짜 정보를 같이 넣어주었다.(pos)

 

이렇게 바꿈으로써 array 함수를 하나 뺄 수 있게 되었지만 역시 시간 초과가 나는데, 그 이유는 shift() 때문이다.

원래 queue에서 하나씩 빼서 사용하곤 했는데, 이 녀석 때문에 시간초과가 걸려 그냥 안 빼고 인덱스 변수를 사용하는 방향으로 잡고 진행하였다.

 

▷ 구현

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

const ds = [[-1, 0], [1, 0], [0, 1], [0, -1]];
const [M, N] = input[0].split(' ').map(Number);
let queue = [];
let visit = [...Array(N)].map(e => Array(M).fill(0));
let count = M * N;
let answer;

// 초기 상태 세팅
for(let i = 1; i < input.length; i++){
  let box = input[i].split(' ').map(Number);

  box.forEach((tomato, pos) => {
    if(tomato === 1) {
      queue.push([i - 1, pos, 0]);
      visit[i - 1][pos] = 1;
      count--;
    }else if(tomato === -1){
      visit[i - 1][pos] = 1;
      count--;
    }
  });
}

let idx = 0;
while(queue.length != idx){
  const [x, y, pos] = queue[idx];
  for(let i = 0 ; i < 4 ; i++){
    const xPos = x + ds[i][0];
    const yPos = y + ds[i][1];

    if(xPos < 0 || yPos < 0 || xPos >= N || yPos >= M) continue;
    if(!visit[xPos][yPos]){
      visit[xPos][yPos] = 1;
      queue.push([xPos, yPos, pos + 1]);
      count--;
    }
  }

  idx++
  answer = pos;
}

console.log(count ? -1 : answer);

 

▷ 복기 :

시간 초과에서 굉장히 헤맸다.

nodeJs 질문 글도 많이 없고, 그래도 shift() 때문이라는 것을 확인하고 나서는 금방 해결되었다.

 

일단 비슷한 형식의 문제들이 많아서 그나마 풀 수 있는 거 같은데, 실버 골드 문제를 위주로 많이 풀어봐야 할 것 같다.