[프로그래머스] Lv 2. 게임 맵 최단 거리 - Javascript 풀이

💡 유형: DFS/BFS

문제 링크

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

구현

상대 팀 진영에 빠르게 도착하는 방법 = 최단 거리 구하기 = BFS

<규칙>

- 상하좌우로 이동 가능, 벽이 있는 자리(0)로는 이동 불가능

- 게임 맵 좌측 상단인 (1,1) -> 배열 인덱스로 표현하면(0,0)에서 시작, 상대방은 게임 맵 우측 하단(n,m)-> 배열 인덱스로 표현하면 (n-1, m-1) 에 있음

- 벽에 가로막혀 상대 팀 진영에 도착할 수 없을 때는 -1 return

 

1. queue를 활용하여 (0,0)부터 탐색을 시작한다. dist를 통해 이동거리를 저장한다.

2. 상,하,좌,우를 확인하고, 1이라면 queue에 넣는다. (dist+1)

3. 방문한 곳은 0으로 바꿔 다시 방문하지 않도록 한다.

4. (n-1,m-1) 좌표에 도착하면 dist를 return 한다.

5. 도착할 수 없는 경우 -1을 return 한다.

 

풀이 

function solution(maps) {
    const n = maps.length;
    const m = maps[0].length;
    const directions = [[-1,0],[1,0],[0,-1],[0,1]]; //상,하,좌,우
    const queue = [[0,0,1]]; //[x,y,거리]
    
    while(queue.length){
        const [x,y,dist] = queue.shift();
        if(x === n-1 && y===m-1) return dist;
        
        for(const [dx,dy] of directions){
            const nx = x + dx;
            const ny = y + dy;
            
           //maps 범위 내에 있고 && 1이면 push
            if(nx>=0 && nx<n && ny>=0 && ny<m && maps[nx][ny]===1){
                queue.push([nx,ny,dist+1]);
                maps[nx][ny] = 0; //재방문 방지
            }
        } 
    }
    
    //도착 불가능한 경우
    return -1;
}

 

BFS의 기본 구현 원리는 다음과 같다.

1. 탐색을 시작하는 정점을 큐에 넣는다.

2. 큐가 비어질 때까지 아래 과정을 반복한다. 

    큐를 가장 앞에 있는 정점(큐에 가장 오래있던 정점)을 뽑아서 그와 연결된 정점을 모두 큐에 넣는다.

 

BFS를 수행할 때는 큐 자료구조를 만들어야함을 기억하자!