994.Rotting Oranges

너비우선 탐색과 동적프로그래밍을 적용시켜 문제를 해결했다.

자바스크립트 풀이

중급 문제이므로 너비우선탐색과 동적 프로그래밍을 안다 생각하고 설명하겠습니다.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function(grid) {
    let que = []; // 너비우선탐색에 사용될 빈 큐
    let m = grid.length; // 그리드의 높이
    let n = grid[0].length; // 그리드의 너비
    let dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]; // 방향 위, 아래, 오른, 왼 쪽을 의미
    let dp = []; // dp[i][j] = grid[i][j]에 있는 싱싱한 오렌지가 썩는데 걸리는 최소시간을 의미
    let check = true; // 후에 설명할 특수한 경우를 체크하기 위한 플래그
    for (let i = 0; i < m; i++) {
        let temp = []; // dp에 들어갈 한 줄을 담을 빈 배열
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 2) { // 만약 현 위치의 오렌지가 썩은 오렌지라면
                que.push([i, j, 0]); // que에 삽입 여기서 0은 시간 0분을 의미 이미 썩었으므로
                temp.push(0); // dp에 0으로 초기화 시켜준다.
            } else if (grid[i][j] == 0) {
                temp.push(null); // 0은 아무것도 없는것을 의미하므로 null 값을 삽입해준다.
            } else {
                temp.push(0); // 마찬가지로 dp에 0으로 초기화
            }
        }
        dp.push(temp);  // 하나의 줄을 삽입
    } // 즉 이 for문을 통해 dp를 오렌지가 있는 위치라면 썩든 썩지않았든 모두 일단 0으로 초기화 시켜주고, 큐에 썩은 오렌지의 위치와 0의 값을 리스트로 묶어 삽입했다.
    let cur; // 현재값, 여기에 정의하는 이유는 마지막 쉬프트된 오렌지가 가장 마지막에 썩을 오렌지를 의미하므로 원하는 값이 여기에 담기게 될 것이다.
    while(que.length) { // 너비우선 탐색 시작
        cur = que.shift(); // 큐의 가장 앞 값을 쉬프트한다.
        if (dp[cur[0]][cur[1]] > cur[2]) { // 만약 dp에 삽입된 현 위치의 오렌지가 썩는 시간보다 현재 큐에서 꺼낸 값이 더 작다면 dp값을 새로 갱신한다.
            dp[cur[0]][cur[1]] = cur[2];
        }
        dir.forEach(d => { // 위, 아래, 오, 왼 탐색
            let next = [cur[0] + d[0], cur[1] + d[1], cur[2] + 1]; // next는 cur의 왼 오 위 아래의 위치와 현 시간 + 1분 을 값으로 가진다.
            if (next[0] >= 0 && next[1] >= 0 && next[0] < m && next[1] < n) { // next의 범위가 유효하다면
                if (grid[next[0]][next[1]] == 1) { // 그리고 next 위치에서의 오렌지가 싱싱하다면
                    grid[next[0]][next[1]] = 2; // next위치에서의 싱싱한 오렌지를 썩게 한다. cur은 썩은 오렌지였으므로
                    que.push(next); // 그리고 next의 오렌지는 썩은 오렌지가 되었으므로 큐에 삽입한다.
                }
            }
        })
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                return -1; // 만약 여전히 싱싱한 오렌지가 있다면 그 오렌지는 영원히 썩지않는 오렌지를 의미
            }
            if (dp[i][j] != null) {
                check = false; // 만약 null이 아닌값이 없다면 여기에는 오렌지 자체가 없다는 것을 의미
            }
        }
    }
    if (check) {
        return 0; // 오렌지가 없다면 0을 리턴
    }
    return cur[2]; // 현재 cur에는 마지막으로 shift된 오렌지가 담겨있으므로 cur[2] 즉 제일 마지막으로 썩은 오렌지의 시간을 반환해준다.
};

확실히 푸는것보다 말로, 글로 설명하는게 훨씬 어려운것 같다. 풀고나서 되돌아보면 아주 기본적인 문제인것 같은데 막상 풀때는 정말 힘들었다. 열심히 해야겠다. 아직도 알고리즘을 풀때 어떻게 접근해서 풀어나가야하는지 어렵다. 뭔가 수학처럼 공식이 필요하고 체계적이지만, 수학보단 추상적인것 같은 그런게 프로그래밍인것 같다.
혹시 이 글을 보시는 다른분들은 알고리즘 풀때 어떻게 공식을 세우고 접근을 하는지 팁을 알려주시면 감사하겠습니다ㅠㅠ