해당 포스팅은 백준 문제인 토마토 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였으며 BFS로 풀이하였다.

---

🍅 문제 요약

보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익을 수 있다.

토마토를 창고에 보관하는 격자모양의 상자가 있으며 각각의 칸에는 익은 토마토들과 익지 않은 토마토들이 있다. 일부의 칸에는 토마토가 들어가있지 않다.

정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

---

🤯 풀이

바킹독님의 풀이를 보고 풀었다. 예전에 도전했다가 실패했던 문제라서 감회가 새롭다 !

위의 슬라이드는 바킹독님께서 만든 자료로, 익은 토마토가 여러 개일 때 BFS를 돌리는 방법에 대해 보여준다.

시작점이 여러개인 BFS를 돌리는 방법은 그냥 모든 시작점을 큐에 넣고 BFS를 돌리면 된다. 위의 슬라이드의 그림을 보면 파란색은 익지 않은 토마토, 초록색은 익은 토마토, 빨간색은 빈 칸을 의미한다. 현재 익은 토마토가 2개가 있는데, 그 2개를 큐에 넣고 BFS를 돌리면 익은 토마토와의 거리가 구해진다.

---

🤔 BFS 성질 - 시작점이 여러 개일 때 ?!

앞서 시작점이 여러 개일 때 모든 시작점을 큐에 넣고 BFS를 돌리면 된다고 하였다. 그런데 어떤 원리로 시작점을 전부 넣을 때 답이 나오는걸까?

이 문제는 여러 개의 시작점에서 모든 지점으로의 거리를 구하는 문제이다.
바킹독님께서 만든 자료를 보면서 BFS 과정을 살펴보자.

먼저 익은 토마토, 즉 거리가 0인 칸들을 큐에 다 넣는다.

이 때 첫 번째 칸(익은 토마토)을 통해 추가되는 칸은 첫 번째 칸으로부터 거리가 1인 이웃한 익지 않은 토마토들이다.

그 다음 칸(익은 토마토)을 통해 추가되는 칸들도 두번째 칸으로부터 거리가 1인 이웃한 익지 않은 토마토들이다.

이제 거리가 0인 칸들은 큐에서 다 빠졌고, 순차적으로 1인 칸들을 pop할텐데 잘 생각해보면 1인 칸들을 pop하는 동안 거리가 2인 칸(맨 처음 익은 토마토와의 거리)들이 쭉 추가될 것이다.

거리가 1인 칸들이 다 빠지고 2인 칸들을 볼 때면 3인 칸들이 쭉 추가될 것이다. 이제 전체적인 큐의 모양을 확인해보시면 이와 같이 BFS를 돌 때 큐에 쌓이는 순서는 반드시 거리 순이게 된다.

---

🎨 구현 방법 + 코드

• q : 익은 토마토의 좌표를 저장할 큐를 빈 배열로 초기화
• dist : board 크기만큼 2차원 배열 생성. 각 원소를 0으로 초기화한 다음, 이후 loop를 통해 익지 않은 토마토는 -1으로 재할당할 것이다.

const q = [];
const dist = [...Array(col)].map(() => Array(row).fill(0));

• board 크기만큼 이중 loop : 익은 토마토와 익지 않은 토마토를 탐색
  • if (board[i][j] === 1) : 익은 토마토일 시 해당 토마토의 좌표를 queue에 넣어 인접한 익지 않은 토마토 탐색
  • if (board[i][j] === 0) : 익지 않은 토마토일 시 dist[i][j]를 -1로 재할당. dist[i][j]가 -1이면 방문하지 않은 익지 않은 토마토이다.

for (let i=0; i < col; i++) {
  for (let j=0; j < row; j++) {
    // 익은 토마토일 시 queue에 넣어 주변 익지않은 토마토 탐색
    if (board[i][j] === 1) {
      q.push([i,j]);
    }
    // 익지 않은 토마토일 시
    if (board[i][j] === 0) {
      dist[i][j] = -1;
    }
  }
}

• head : 참조하고 있는 큐의 idx. 해당 문제를 풀 때 shift 메소드를 이용하면 시간 초과나게 된다. 따라서 head 포인터를 이용해서 큐의 value를 탐색한다.
• while (q.length > head) : 큐에는 익은 토마토만 있다. head가 큐의 사이즈보다 작을 때까지만 BFS를 돈다.
  • if (dist[nx][ny] >= 0) continue : 현재 참조하는 큐의 원소 중 인접하는 원소가 익은 토마토 or 빈칸일 시 continue. dist[nx][ny]가 -1(방문하지 않은 익지 않은 토마토)일 때만 아래 로직을 수행한다.
  • dist[nx][ny] = dist[x][y] + 1 : dist[nx][ny]가 -1일 때 방문하지 않은 익지 않은 토마토이므로 현재 참조하는 큐의 원소의 값에서 +1을 해준다. 즉 거리를 +1 해주는 것이다.
  • q.push([nx,ny]) : 해당 원소는 이제 익은 토마토이다. 주변에 방문하지 않은 익지 않은 토마토가 있는지 탐색하기 위해 queue에 넣어준다.

let head = 0;
// 익은토마토만 q에 있음
while (q.length > head) {
  const [x,y] = q[head++];
  for (let k=0; k<4; k++) {
    const nx = x + dx[k];
    const ny = y + dy[k];
    if (nx < 0 || ny < 0 || nx >= col || ny >= row) continue;
    // 익은 토마토 / 빈칸일시 넘어가기
    if (dist[nx][ny] >= 0) continue;
    // 익지않은 토마토에 대해 +1
    dist[nx][ny] = dist[x][y] + 1;
    // 주변 토마토 탐색
    q.push([nx,ny]);
  }
}

• day : 토마토가 익을 때까지의 최소 날짜
• board 크기만큼 2중 loop : 2중 loop를 돌리면서 토마토가 익을 때까지 최소 날짜 탐색

// 토마토가 익을 때까지의 최소 날짜 출력
let day = 0;
for (let i=0; i < col; i++) {
  for (let j=0; j < row; j++) {
    // 익지 않은 토마토가 있음
    if (dist[i][j] === -1) return -1;
    day = Math.max(day, dist[i][j]);
  }
}
return day;

---

🌻 전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').map(s => s.split(" ")).slice(0,-1);
const NM = input.shift();
const [n,m] = NM.map(el => Number(el));
const board = input.map(s => s.map(el => Number(el)));

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

function solution(row,col,board) {
    const q = [];
    const dist = [...Array(col)].map(() => Array(row).fill(0));
    for (let i=0; i < col; i++) {
        for (let j=0; j < row; j++) {
            // 익은 토마토일 시 queue에 넣어 주변 익지않은 토마토 탐색
            if (board[i][j] === 1) {
                q.push([i,j]);
            }
            // 익지 않은 토마토일 시
            if (board[i][j] === 0) {
                dist[i][j] = -1;
            }
        }
    }
    let head = 0;
    // 익은토마토만 q에 있음
    while (q.length > head) {
        const [x,y] = q[head++];
        for (let k=0; k<4; k++) {
            const nx = x + dx[k];
            const ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= col || ny >= row) continue;
            // 익은 토마토 / 빈칸일시 넘어가기
            if (dist[nx][ny] >= 0) continue;
            // 익지않은 토마토에 대해 +1
            dist[nx][ny] = dist[x][y] + 1;
            // 주변 토마토 탐색
            q.push([nx,ny]);
        }
    }
    
    // 토마토가 익을 때까지의 최소 날짜 출력
    let day = 0;
    for (let i=0; i < col; i++) {
        for (let j=0; j < row; j++) {
            // 익지 않은 토마토가 있음
            if (dist[i][j] === -1) return -1;
            day = Math.max(day, dist[i][j]);
        }
    }
    return day;
}

console.log(solution(n,m,board));

---

(ref) 바킹독님의 풀이