[JS로 코테 준비하기] 11. 프로그래머스 - 안전지대 (feat. 2차원 배열 탐색 관련)

https://school.programmers.co.kr/learn/courses/30/lessons/120866

프로그래머스

 

JS로 2차원 배열을 다루는 데 필요한 기본적인 꿀팁들을 많이 얻어갈 수 있는 문제였다.

 

1. 2차원 배열의 깊은 복사

2차원 배열을 탐색하는 문제에서 주어진 기존 배열은 그대로 두고, 새로운 배열을 만들어야 하는 경우가 있다. 

이때 새로운 배열이 기존 배열과 엮기지 않도록! 완전히 독립적 이도록! 깊은 복사를 해야한다.

 

일반적으로 1차원 배열의 깊은 복사는 slice()를 활용한다.

const arr = [1, 2, 3, 4];
const copy = arr.slice();

 

하지만 다차원 배열에 slice()를 활용하면, 얕은 복사가 된다.

다차원 배열과 객체의 깊은 복사는 JSON.parse()와 JSON.stringify()를 사용해야 한다.

const arr = [[0, 0, 0], [1, 0, 1], [0, 1, 1]];
const copy = JSON.parse(JSON.stringify(arr));

 

이 부분은 알고리즘을 풀면서 굉장히 자주 쓰일 것이다. 나올 때마다 찾아보지 않도록 외워둬야겠다. 특정 개념 혹은 상황을 JS 코드로 구현하는 방식을 알아두어야 빠르게 풀이가 가능하기 때문이다. (단점: js 코드를 하나 넣을 때마다 c++ 코드는 까먹음ㅠ)

 

 

참고) 2차원 배열 생성

const visited = Array.from(Array(n), () => Array(n).fill(false));

 

참고) 얕은 복사 vs 깊은 복사

• 얕은 복사: 기존 배열의 값과 주소를 공유한다. 두 배열 중 한 곳에서 변경이 일어났을 때 다른 배열도 변경된다.
• 깊은 복사: 기존 배열의 값만 복사하며 별도의 주소를 가진다. 각 배열의 변경은 다른 배열과 무관한다. 

 

 

2. 탐색 방향 

2차원 배열 탐색을 위한 방향을 설정할 때, 항상 x축과 y축을 나눠서 표현했었다. 

그런데 이번에 다른 사람들 풀이에서 2차원 배열로 방향을 한 번에 나타내는 것을 보았다.

 

정답은 없지만, 한 줄로 나타내는 것도 꽤 괜찮은 방법 같다.

//원래는 이렇게 했는데
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

//이렇게도 가능
const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];

 

 

3. ?. 활용 풀이

다른 사람의 풀이를 보다가 JS의 특성을 제대로 살린, ?.를 활용한 코드를 보았다.

컴포넌트를 개발할 때는 자연스럽게 쓰는 옵셔널 체이닝을 알고리즘에서는 왜 사용할 생각을 못했을까 싶었다.

 

풀이는 여기서 확인할 수 있다. 배열의 경계를 ?.로 처리한 것 같은데, 방향을 꼭 한 번에 써야만 가능한지 의문이다. 기존 코드에서 이를 활용해 보려고 이것저것 해봤는데, 엉망이 되어서 포기했다. 나중에 다시 시도해 볼 예정이다.

 

 

4. 소스코드

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

function solution(board) {
    const n = board.length;
    const danger = JSON.parse(JSON.stringify(board)); //깊은 복사

    for(let x = 0; x < n; x++){
        for(let y = 0; y < n; y++){
            if(!board[x][y]) continue;
            
            for(let i = 0; i < 8; i++){
                const nx = x + dx[i];
                const ny = y + dy[i];
                
                if(nx < 0 || nx >= n || ny < 0 || ny >= n)
                    continue;
                
                danger[nx][ny] = 1;
            }
        }
    }
    
    const mineCnt = danger.flat().filter(d => d).length;
    return n * n - mineCnt;
}

 

 

Reference

• https://developer-talk.tistory.com/325