[프로그래머스/JS] Lv2. 게임 맵 최단거리 (큐 구현 방식)

문제

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

프로그래머스

---

풀이

전형적인 BFS 문제이지만, 자바스크립트로 풀려니 구현 방식에서 고민이 많이 되었다.

 

우선 처음 작성한 코드를 살펴보며 자바와 다르게 고민했던 부분들을 정리해보겠다.

function solution(maps) {
    var answer = -1;
    const N = maps.length;
    const M = maps[0].length;
    const dr = [-1,1,0,0];
    const dc = [0,0,-1,1];
    
    //1.
    let visited = Array.from(Array(N), () => new Array(M).fill(false));
    
    bfs();
    
    function bfs(){
        let queue = new Queue();
        
        //2
        queue.add([0,0,1]);
        visited[0][0] = true;
        
        while(!queue.isEmpty()){
            const cur = queue.poll();
            
            const r = cur[0];
            const c = cur[1];
            const cnt = cur[2];
            
            if(r==N-1&&c==M-1){
                answer = cnt;
                break;
            }
            
            for(let d = 0; d<4;d++){
                let idr = r + dr[d];
                let idc = c + dc[d];
            
                if(idr<0||idc<0||idr>=N||idc>=M) continue;
                if(maps[idr][idc]===0) continue;
                if(visited[idr][idc]) continue;
                visited[idr][idc] = true;
                queue.add([idr, idc, cnt+1]);
            }
        }
    }
    
    return answer;
}

//3
class Queue{
    constructor(){
        this.storage = {};
        this.head = 0;
        this.tail = 0;   
    }
    add(item){
        this.storage[this.tail++] = item;
    }
    poll(){
        let removed = this.storage[this.head];
        delete this.storage[this.head];
        this.head++;
        
        if(this.head===this.tail){
            this.head=0;
            this.tail=0;
        }
        return removed;
    }
    isEmpty(){
        return this.tail-this.head===0;
    }
}

 

 

 

세 가지 부분을 고민했는데, 우선 방문 배열을 채우는 부분이다.

 

이 문제에서는 방문 배열이 반드시 필요하지는 않지만, 다른 bfs 문제들에 많이 쓰여서 구현해보았다. 사실 고민이라기보다는 문법을 잘 몰랐다. 위에서 보듯이, 아래와 같은 코드로 방문 배열을 초기화할 수 있었다.

    let visited = Array.from(Array(N), () => new Array(M).fill(false));

 

 

두 번째는 큐를 구현하는 방식이다.

 이전에 큐를 구현했을 때, 내부적으로 배열의 shift 메서드로 인해 시간초과가 발생했다. shift는 한 칸씩 당기는 기능때문에 시간복잡도가 O(n)이 소요된다.

 

그래서 자바의 JCF에서 ArrayDeque를 구현하는 방식과 비슷하게 tail과 head라는 인덱스를 두어 선언했다.

class Queue{
    constructor(){
        this.storage = {};
        this.head = 0;
        this.tail = 0;   
    }
    add(item){
        this.storage[this.tail++] = item;
    }
    poll(){
        let removed = this.storage[this.head];
        delete this.storage[this.head];
        this.head++;
        
        if(this.head===this.tail){
            this.head=0;
            this.tail=0;
        }
        return removed;
    }
    
    isEmpty(){
        return this.tail-this.head===0;
    }
}

 

 

 

마지막은 queue에 인자값을 어떻게 넣어야할지 고민했다. 자바스크립트는 자료형에 대해 엄격하지 않았는데, 그것때문에 더 헷갈렸던 것 같다. 결국 queue에는 배열로 값을 삽입했다.

 

 

 

그런데 풀고나서 다른 소스 코드들을 보니 큐 구현체를 굳이 사용하지 않아도 되구나 싶었다. 자바스크립트 배열 메서드인 shift() 덕분이다. shift를 쓰면 배열도 큐처럼 사용할 수  있다.

 

 

아래는 구현체를 쓰지않고, 배열과 shift 메서드를 통한 풀이이다.

---

소스 코드

function solution(maps) {
    var answer = -1;
    const N = maps.length;
    const M = maps[0].length;
    
    const dr = [-1,1,0,0];
    const dc = [0,0,-1,1];
    let visited = Array.from(Array(N), () => new Array(M).fill(false));
    
    bfs();
    
    function bfs(){
        let queue = [[0,0,1]]; // queue.add([0,0,1]);
        visited[0][0] = true;
        
        while(queue.length){ //!queue.isEmpty();
            const [r,c,cnt] = queue.shift();
            // const cur = queue.poll();
            // const r = cur[0];
            // const c = cur[1];
            // const cnt = cur[2];
            
            if(r==N-1&&c==M-1){
                answer = cnt;
                break;
            }
            for(let d = 0; d<4;d++){
                let idr = r + dr[d];
                let idc = c + dc[d];
            
                if(idr<0||idc<0||idr>=N||idc>=M) continue;
                if(maps[idr][idc]===0) continue;
                if(visited[idr][idc]) continue;
                visited[idr][idc] = true;
                queue.push([idr, idc, cnt+1]);
            }
        }
    }
    return answer;
}