[백준7576_자바스크립트(javascript)] - 토마토

🔴 문제

토마토
이 문제는 토마토 7576번을 다루고 있습니다. 7569의 풀이는 여기에서 볼 수 있습니다.

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [mn, ...input] = fs.readFileSync(path).toString().trim().split('\n');
const [m, n] = mn.split(' ').map(Number);
const map = input.map((it) => it.split(' ').map(Number));

const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

let q = [];
let front = 0;

// 1. 시작점 찾기
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (map[i][j] === 1) q.push([i, j]);
  }
}

while (front < q.length) {
  const [x, y] = q[front++];

  for (let i = 0; i < 4; i++) {
    const nx = dx[i] + x;
    const ny = dy[i] + y;

    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
    if (map[nx][ny] === 0) {
      map[nx][ny] = map[x][y] + 1;

      q.push([nx, ny]);
    }
  }
}

const answer = map.flat();

if (answer.includes(0)) {
  console.log(-1);
} else {
  console.log(Math.max(...answer) - 1);
}

🟢 풀이

⏰ 소요한 시간 : 2h++

이 토마토는 일반적인 bfs에서 조금 응용되는 문제인데 시작지점이 여러 곳이기 때문이다. 이 경우 시작할 때 큐에 모든 값을 넣고 시작해 주면된다. 위 코드의 1번 위치에서 시작점을 모두 찾아서 큐에 넣어준다.
그리고 보통은 큐가 빌 때까지 반복을 하게되는데 큐가 빌 때까지 구현하고 모든 좌표를 shift() 하게되면 시간 초과가 발생한다. 맨 앞의 요소를 제거하고 모든 인덱스를 한 칸씩 땡겨줘야 하기 때문이다. 따라서 맨앞의 요소를 제거하지 않고 현재 요소를 가르키는 front 변수를 하나 만들어 인덱싱 해준다. 따라서 따라서 큐에 있는 요소의 개수가 front 보다 작아지면 반복을 종료해야 한다.
그 이후로는 일반적인 bfs처럼 상하좌우 돌면서 범위를 체크하고 익지 않은 토마토라면 방문 처리를 해주면 된다.
bfs 순회를 다 끝내고 마지막으로 정답을 출력할 때 익지 않은 토마토인 0이 있다면 -1을 출력해주고 0이 없다면 최대값에서 1을 뺀 날짜를 출력해 주면 된다.

내가 이 문제를 못풀었던 이유는
1. 모든 시작점을 시작할때 한 번에 넣어줄 생각을 못했고
2. shift() 사용없이 front 변수를 사용해서 접근할 생각을 못했고
3. 방문처리를 하면서 동시에 해당 위치에 소요 일을 저장할 생각을 못했다.

문제를 풀고나니 bfs에서 조금 응용을 더한 아주 좋은 문제 같다.
난 못풀었지만 ..

🔵 Ref

https://velog.io/@dev-redo/%EB%B0%B1%EC%A4%80-7576%EB%B2%88-%ED%86%A0%EB%A7%88%ED%86%A0-NodeJS#-%EC%A0%84%EC%B2%B4-%EC%BD%94%EB%93%9C