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

2024. 7. 2. 21:45· JavaScript/프로그래머스

문제

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr


풀이

전형적인 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;
}

 

 

'JavaScript > 프로그래머스' 카테고리의 다른 글

[프로그래머스/JS] Lv2. 더 맵게 (힙 자료구조, 우선순위 큐 구현)  (0) 2024.06.27
[프로그래머스/JS] Lv1. 올바른 괄호 (스택 구현)  (0) 2024.06.26
[프로그래머스/JS] Lv1. 같은 숫자는 싫어  (1) 2024.06.26
[프로그래머스/JS] Lv0. 문자열 반복해서 출력하기 (반복 출력)  (0) 2024.06.21
[프로그래머스/JS] Lv0. a와 b 출력하기 (구조 분해 할당)  (0) 2024.06.21
'JavaScript/프로그래머스' 카테고리의 다른 글
  • [프로그래머스/JS] Lv2. 더 맵게 (힙 자료구조, 우선순위 큐 구현)
  • [프로그래머스/JS] Lv1. 올바른 괄호 (스택 구현)
  • [프로그래머스/JS] Lv1. 같은 숫자는 싫어
  • [프로그래머스/JS] Lv0. 문자열 반복해서 출력하기 (반복 출력)
동구름이
동구름이
동구름이
동구름
동구름이
전체
오늘
어제
  • 분류 전체보기 (178)
    • Java (63)
      • Java 를 파헤쳐보자 (13)
      • BOJ (45)
      • 프로그래머스 (3)
      • SWEA (1)
      • Java GUI (1)
    • JavaScript (17)
      • JS를 파헤쳐보자 (7)
      • 프로그래머스 (7)
      • JS 학습 정리 (1)
    • Backend (33)
      • Spring (3)
      • HTTP (7)
      • 프로젝트 (10)
      • MySQL (6)
      • Redis (3)
      • Elastic Search (1)
      • 인증, 인가 (3)
    • CS (57)
      • 운영체제 (35)
      • Network (22)
    • Git (2)
    • 개발 관련 이것저것 (2)
    • etc (1)
    • 독서 (0)
    • 사설 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 스택
  • 프로그래머스
  • 백준
  • 자바스크립트
  • OS
  • Java
  • 모든 개발자를 위한 HTTP 웹 기본 지식
  • 이석복
  • 자바
  • 구현
  • 김영한
  • 큐
  • 네트워크
  • 레디스
  • 반효경
  • JCF
  • 인프런
  • 한양대
  • 운영체제
  • BOJ

최근 글

hELLO · Designed By 정상우.v4.2.2
동구름이
[프로그래머스/JS] Lv2. 게임 맵 최단거리 (큐 구현 방식)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.