542. 01 Matrix

https://leetcode.com/problems/01-matrix/

01 Matrix - LeetCode

---

특정 셀에서 가장 가까운 0까지의 거리

 

다른 사람 풀이

https://leetcode.com/problems/01-matrix/discuss/314774/Heavily-commented-JavaScript-solution-using-BFS

Heavily commented JavaScript solution using BFS - LeetCode Discuss

셀에 0이 있는 경우, 주변에 '전염병'이 퍼진다고 생각하자. 그리고 이 전염병은 떨어진 거리만큼 그 정도가 약해진다.

 

초록색은 1만큼 퍼진 경우, 노란색은 2만큼 퍼진 경우, 보라색은 3만큼 퍼진 경우(depth라고 생각하면 이해가 빠를듯?)이며, '전염' 컨셉을 구현하기 위해 Queue를 사용했다.

 

 

 

행렬에서 차례 개념인 Queue의 등장은 낯설지만, 0으로 부터 떨어진 거리가 같은 애들을 '순 서 대 로' 방문하기 위해 사용한다. 그러므로 전염병은 '동시다발적'으로 퍼진다.

 

 

풀이는 모든 1을 무한대로 바꿈으로써, 다른 0에서의 방문 여부를 확인하기 쉽게 한다. 그렇다면 이러한 방법을 사용하지 못하는 경우, 행렬을 하나 더 만들고, 그 행렬을 채워나간 후 return하는 방식을 생각한다. 복사한 행렬의 특정 셀이 비어있는 경우, 해당 셀은 방문하지 않은 셀이다.

 

    while (queue.length) {
        let [curX, curY, curValue] = queue.shift();

        for (let [x, y] of dires) {
            let moveX = curX + x;
            let moveY = curY + y;
            if(moveX < 0 || moveX >= row || moveY < 0 || moveY >= col) continue; // 행렬 범위를 벗어난 경우,
            else {
                if(mat[moveY][moveX] === 1 && !dupl[moveY][moveX]) { // 복사한 행렬이 비어있는 경우,
                    dupl[moveY][moveX] = curValue + 1;
                    queue.push([moveX, moveY, curValue + 1]);
                }
            }
        }
    }