[프로그래머스] 게임 맵 최단거리(LV.2) by javascript - 찾아라 프로그래밍 마에스터

▷ 문제 : 찾아라 프로그래밍 마에스터 - 게임 맵 최단거리 LV.2

코딩테스트 연습 - 게임 맵 최단거리

▷ 해결 날짜 : 2022.05.15
▷ 소요 시간 : 40분
▷ 풀이 과정 :

문제는 전형적인 그래프 탐색 알고리즘 문제다.

결국 최단거리를 찾아야 하기 때문에 BFS 탐색 알고리즘을 사용하면 된다.

 

상하좌우 어디로든 갈 수 있기 때문에 방향을 체크해줄 ds를 선언

그리고 방문을 체크해줄 visit을 선언 이 visit 변수를 통해 최종 값을 반환해줄 것이다.

이런 식으로 초기값을 만들어두고

 

모든 위치를 탐색할 때까지 반복문을 돌려주면 해결되는 문제다.

 

▷ 구현

function solution(maps) {
    const ds = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const [n, m] = [maps.length, maps[0].length];
    const visit = Array.from(Array(n), e => Array(m).fill(0));
    visit[0][0] = 1;

    let idx = 0;
    const queue = [[0, 0]];
    while(queue.length != idx){
        const [posX, posY] = queue[idx];
        for(let i = 0; i < ds.length; i++){
            const [newX, newY] = [posX + ds[i][0], posY + ds[i][1]];
            if(newX < 0 || newY < 0 || newX >= n || newY >= m) continue;
            if(!visit[newX][newY] && maps[newX][newY]){
                visit[newX][newY] = visit[posX][posY] + 1;
                queue.push([newX, newY]);
            }
        }
        idx++;
    }

    return visit[n - 1][m - 1] ? visit[n - 1][m - 1] : -1; 
}

▷ 복기 :

기본적인 시작점부터 도달점까지의 최단거리 탐색 문제이기 때문에 그렇게 큰 어려움은 없었다.