자바스크립트로 푸는 썩는 토마토 문제: BFS로 최소 경과 시간 구하기

문제 정의

숫자로 이루어진 2차원 배열 arr를 유일한 인수로 받아 처리하는 자바스크립트 함수를 작성해야 합니다.

배열의 각 숫자는 다음과 같은 의미를 가집니다.

• 0: 빈 칸을 나타냅니다.
• 1: 신선한 토마토를 나타냅니다.
• 2: 썩은 토마토를 나타냅니다.

매 분마다 썩은 토마토와 상하좌우 4방향으로 인접해 있는 신선한 토마토는 함께 썩게 됩니다.

따라서 함수는 격자에 신선한 토마토가 하나도 남지 않을 때까지 경과해야 하는 최소 시간(분)을 반환해야 하며, 모든 토마토를 썩히는 것이 불가능한 경우에는 대신 -1을 반환해야 합니다.

입력 예시

const arr = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1]
];

위 입력에 대한 기대 출력은 다음과 같습니다.

const output = 4;

출력 과정 설명

분이 지날 때마다 배열의 상태는 아래 표처럼 변화합니다. 4분이 경과하면 신선한 토마토가 모두 썩게 되므로 정답은 4입니다.

[2, 2, 1]
[2, 1, 0]
[0, 1, 1]

[2, 2, 2]
[2, 2, 0]
[0, 1, 1]

[2, 2, 2]
[2, 2, 0]
[0, 2, 1]

[2, 2, 2]
[2, 2, 0]
[0, 2, 2]

접근 방식: 너비 우선 탐색(BFS)

이 문제는 흔히 '썩은 오렌지(Rotting Oranges)' 문제로도 알려져 있으며, 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 풀이 절차는 다음과 같습니다.

1. 격자를 한 번 순회하면서 신선한 토마토의 개수(fresh)와 초기 썩은 토마토들의 위치(curr)를 수집합니다.
2. 처음부터 신선한 토마토가 없다면 즉시 0을 반환합니다.
3. curr 큐에 담긴 썩은 토마토를 기준으로 상하좌우를 검사하고, 아직 신선한 이웃 토마토를 썩혀서 next 배열에 추가합니다.
4. 한 라운드가 끝날 때마다 경과 시간(count)을 1씩 증가시키고, next 배열을 새로운 curr로 교체합니다.
5. 큐가 비었을 때 fresh가 0이라면 count를, 그렇지 않다면 도달하지 못한 신선한 토마토가 있다는 뜻이므로 -1을 반환합니다.

구현 코드

const arr = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1]
];
const timeToRot = (arr = []) => {
    let fresh = 0;
    let count = -1;
    let curr = [];
    for(let i = 0; i < arr.length; i++){
        for(let j = 0; j < arr[i].length; j++){
            if(arr[i][j] === 1){
                fresh += 1;
            };
            if(arr[i][j] === 2){
                curr.push([i, j]);
            };
        };
    };
    if(!fresh){
        return 0;
    };
    while(curr.length > 0){
        count += 1;
        const next = [];
        const rotten = (i, j) => {
            arr[i][j] = 2
            next.push([i, j])
            fresh -= 1
        };
        for(const [i, j] of curr){
            if (arr[i - 1] && arr[i - 1][j] === 1) {
                rotten(i - 1, j);
            };
            if (arr[i + 1] && arr[i + 1][j] === 1) {
                rotten(i + 1, j);
            };
            if (arr[i][j - 1] === 1) {
                rotten(i, j - 1);
            };
            if (arr[i][j + 1] === 1) {
                rotten(i, j + 1);
            };
        }
        curr = next
    };
    return fresh === 0 ? count : -1;
};
console.log(timeToRot(arr));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.

4