[프로그래머스/js] 게임 맵 최단거리 (Lv. 2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=javascript

`프로그래머스 :: 게임 맵 최단거리 :: Lv. 2`

 

문제 리뷰

오늘은 재미있는 '델타 탐색' 문제를 찾아왔습니다. ㅋ

 

자바로는 한 번 풀어봤던 문제인데요..

재미있는 js로도 풀어보기 위해 오랜만에 다시 건드렸습니다.

 

델타 탐색 문제가 뭐냐?

2차원 배열에서, 어떤 기준 값으로부터 상·하·좌·우 방향으로 한 칸 씩 미리 확인해보면서 탐색해야 하는 문제를 말합니다.

 

아주 상하좌우로 탐색해보고 싶은 그림이라는 게 보이실 겁니다. (< 네?)

 

첫 번째 시도 (정답)

code

const delta = [[1, 0], [0, 1], [-1, 0], [0, -1]];

function solution(maps) {
    let queue = [];
    queue.push([0, 0, 1]); // x, y, distance
    
    while (queue.length > 0) {
        const [x, y, distance] = queue.shift();
        
        for (const [dx, dy] of delta) {
            if (
                x + dx >= 0 && x + dx < maps.length &&
                y + dy >= 0 && y + dy < maps[0].length &&
                maps[x + dx][y + dy] === 1
            ) {
                maps[x + dx][y + dy] = distance + 1;
                queue.push([x + dx, y + dy, maps[x + dx][y + dy]]);
            }
        }
    }
    
    return maps[maps.length - 1][maps[0].length - 1] <= 1 ? -1 : maps[maps.length - 1][maps[0].length - 1];
}

 

review

const delta = [[1, 0], [0, 1], [-1, 0], [0, -1]];

 

이 방향 배열에 대해서는 아래 그림처럼 연상할 수 있으면 됩니다..

 

 

첫 번째 시도 채점 결과

두 번째 시도 (정답) - Queue 구현

code

const delta = [[1, 0], [0, 1], [-1, 0], [0, -1]];

function solution(maps) {
    let queue = new Queue();
    queue.enqueue([0, 0, 1]); // x, y, distance
    
    while (!queue.isEmpty()) {
        const [x, y, distance] = queue.dequeue();
        
        for (const [dx, dy] of delta) {
            if (
                x + dx >= 0 && x + dx < maps.length &&
                y + dy >= 0 && y + dy < maps[0].length &&
                maps[x + dx][y + dy] === 1
            ) {
                maps[x + dx][y + dy] = distance + 1;
                queue.enqueue([x + dx, y + dy, maps[x + dx][y + dy]]);
            }
        }
    }
    
    return maps[maps.length - 1][maps[0].length - 1] <= 1 ? -1 : maps[maps.length - 1][maps[0].length - 1];
}

class Queue {
    constructor() {
        this.queue = [];
        this.head = 0;
        this.tail = 0;
    }
    
    enqueue(value) {
        this.queue.push(value);
        this.tail++;
    }
    
    dequeue() {
        const returnValue = this.queue[this.head];
        this.head++;
        return returnValue;
    }
    
    isEmpty() {
        return this.tail - this.head === 0;
    }
}

 

review

두 번째 시도 채점 결과

혹시 제 블로그를 지켜보던 분이 계시다면

제가 Queue를 구현해서 또 풀어볼 것이라는 것까지 예상하셨을 것 같습니다. (^//^)

 

다른 로직은 모두 동일한데,

const queue에서 JS Array와 shift()를 사용하지 않고

Queue class를 구현한 모습입니다.

 

소감

첫 번째 시도 (정답)	두 번째 시도 (정답) - Queue 구현
첫 번째 시도 채점 결과	두 번째 시도 채점 결과

 

이렇게 비교해 보면, 이 문제에서는 Queue를 직접 구현하기 보다는 JS Array를 사용한 방법이

미세하지만 효율이 더 좋아보입니다.

 

이것도 제 블로그를 지켜보신 분이라면 많이 보던 얘기구만 싶으실 텐데요 (ㅋ)

shift() 가 길이가 n인 배열에 대해서 시간 복잡도가 O(n) 이긴 하지만,

어느정도까지는 js에서 최적화가 되기 때문에

직접 구현한 Queue의 좋은 성적을 낼 수 있다!

라고 합니다.

 

큐 구현이 분명 필요한 때가 있을 테니 틈날 때마다 연습해 놓아야 합니다!!!!!!!

이상입니다.