[프로그래머스] 게임 맵 최단거리 (level2, JavaScript)

문제

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

BFS로 푼 이유?

DFS(깊이 우선 탐색)로 풀어버리면 모든 노드를 다 방문한 경로가 최단거리가 아닐 수도 있지만 BFS(너비 우선 탐색)으로 풀면 현재 노드에서 가까운 노드부터 찾기 때문에 탐색 시 먼저 찾아지는 경로가 최단거리라서 미로찾기나 최단거리를 구하는 문제일 경우 BFS를 사용해야한다.

나의 풀이

function solution(maps) {
    //정답 제출용 변수 answer 
    let answer = -1;
    const n= maps.length;
    const m = maps[0].length;

    //x,y축이 움직여야하기 때문에 (상,하,좌,우) 배열 저장
    const move_x = [0, 0, 1, -1];
    const move_y = [1, -1, 0, 0];

    // bfs를 돌리기 위해 queue에 초기값 저장, queue[2]는 이동거리리
    const queue = [[0, 0, 1]];

    //bfs 돌림
    while (queue.length) {
        //  현재 값에 큐값을 꺼낸다.
        const now_q = queue.shift();

        // 현재 위치에서 상,하,좌,우 이동할 반복문
        for (let i = 0; i < 4; i++) {
            const new_y = now_q[0] + move_y[i];
            const new_x = now_q[1] + move_x[i];
            
            //new_x와 new_y가 주어진 배열의 범위 안에 있고, 아직 방문하지 않았다면(아직 1이라면)
            if (new_x >= 0 && new_y >= 0 && new_x < m && new_y < n && maps[new_y][new_x] === 1) {
                //방문표시를 위해 방문한 위치는 0으로 바꿔줌
                maps[new_y][new_x] = 0;
                
                //큐에 해당 값을 넣어주고, now_q[2](이동거리)를 1씩 증가해준다.
                queue.push([new_y, new_x, now_q[2] + 1]);    
            }
        }

         //꺼낸 값이 도착지([n-1][m-1])라면 이동거리를 리턴한다.
         if (now_q[0] === n - 1 && now_q[1] === m - 1) {
            answer = now_q[2]
            return answer;
        }
    }
    
    //도착지까지 가지 못했다면(도착지를 갈 수 없다면) 처음 answer에 넣어둔 -1를 리턴 
    return answer;
}

느낀점

평소 프로그래머스 레벨1이나 레벨2 정답률 높은 문제 정도만 풀었고 자료구조에대한 지식이 없던 나에겐 bfs 구현은 좀 어려워 문제 푸는데 오래 걸렸다... 1시간만에 푸신 분들 대단한거같다..
레벨 3은 대체 어떻게 풀지 막막하다... 자료구조... 열심히 해야겠다... ㅠ.ㅠ