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

문제

창고의 토마토들이 모두 익게되는 최소 일수를 출력합니다.
모두 익지 못하는 상황이면 -1을 출력합니다.

구현

문제를 풀면서 마주한 이슈와 해결한 방법들을 위주로 정리했습니다.

1. BFS

• 토마토를 만날 때마다 BFS 수행 -> X, 시간초과
• 모든 토마토를 queue에 push후에 BFS 수행 -> O

만약 아래와 같이 토마토를 만날때마다 BFS를 수행하면 방문한 곳을 또 방문하면서 더 작은 값으로 업데이트 해야 합니다.

for [r, c] in graph
  if graph[r][c] === 1
    queue.push([r, c])
    BFS(queue)

예제3을 예로 들어보면 각 1의 위치에서 BFS를 수행하면서 -1과 1을 제외한 칸을 더 작은 값으로 업데이트 합니다.

1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

// [0, 0]에서 BFS
1 -1 7 8 9 10
2 -1 6 7 8 9
3 4 5 6 -1 10
4 5 6 7 -1 1

// [3, 5]에서 BFS
1 -1 7 6 5 4
2 -1 6 5 4 3
3 4 5 6 -1 2
4 5 6 7 -1 1

위의 방법은 테스트케이스는 통과하지만 배열의 크기가 커지면 시간초과가 발생합니다. 따라서 모든 토마토를 queue에 push하고 BFS를 수행합니다. 이때 이전에 방문한 곳은 다시 방문하지 않도록 합니다.

2. 토마토가 모두 익지 못하는 상황

토마토가 모두 익지 못하는 상황에는 -1을 출력해야 합니다. 이는 그래프에 속하는 -1의 개수와 BFS를 수행한 좌표의 개수의 합이 그래프의 넓이(R*C)와 같은지로 판별합니다. 만약 그래프의 넓이보다 작다면 BFS로 방문하지 못한 좌표가 있다는 것을 의미하고, 이는 '토마토가 모두 익지 못하는 상황'이므로 -1을 출력합니다.

3. shift함수 피하기

array의 shift 연산은 배열 맨 앞의 요소를 제거하지만, 나머지 요소들의 인덱스를 한 칸씩 앞으로 당기기 때문에 시간복잡도는 O(1)이 아닙니다. 따라서 인덱스를 이용하는 방식으로 변경했습니다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n');
const tmp = input[0]
  .trim()
  .split(' ')
  .map((x) => Number(x));
const C = tmp[0];
const R = tmp[1];
const graph = input.slice(1).map((x) =>
  x
    .trim()
    .split(' ')
    .map((y) => Number(y))
);
const visit = Array.from({ length: R }, () => Array(C).fill(0));
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
let answer = 1;
let count = 0;
let queue = [];
for (let i = 0; i < R; i++) {
  for (let j = 0; j < C; j++) {
    if (graph[i][j] === 1) {
      visit[i][j] += 1;
      queue.push([i, j]);
      count += 1;
    } else if (graph[i][j] === -1) {
      count += 1;
    }
  }
}
while (queue.length) {
  const repeat = queue.length;
  for (let i = 0; i < repeat; i++) {
    const r = queue[i][0];
    const c = queue[i][1];
    for (let k = 0; k < 4; k++) {
      const nr = r + dr[k];
      const nc = c + dc[k];
      if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
        continue;
      } else if (graph[nr][nc] === -1) {
        continue;
      } else if (
        visit[nr][nc] === 0
      ) {
        visit[nr][nc] = +1;
        queue.push([nr, nc]);
        graph[nr][nc] = graph[r][c] + 1;
        answer = Math.max(graph[nr][nc], answer);
        count += 1;
      }
    }
  }
  queue = queue.slice(repeat);
}
if (count !== R * C) {
  console.log(-1);
} else {
  console.log(answer - 1);
}