[Algorithm] 프로그래머스 - 게임 맵 최단거리

문제

[프로그래머스] 게임 맵 최단거리

사용 알고리즘

- 너비우선탐색 (Breath-First Search)

해결방법

• BFS사용해서 풀면 되는데, 결국 문제에서 구해야 하는 것은 최단 경로로 이동했을 때의 길이이므로, 방문을 체크하는 visited 배열에 길이를 저장해주도록 한다
• 그래프에서 상,하,좌,우 로 이동이 가능하므로 4방향 이동을 간단하게 표현하기 위해 dir 배열을 만들어 사용
• needVisit배열이 BFS의 큐로 보면 되고, 이때 FIFO이므로 while 루프에서 꺼낼 때 shift() 메소드를 사용해 먼저 들어온 것 부터 체크
• 방문하지 않은 지점 (visited배열의 값이 0) 혹은, 이미 방문한 지점이지만 현재 위치에서 한 칸 이동한 것의 길이가 더 최단일 경우 큐(needVisit)에 넣어 다시 탐색

위치별 최단 이동 거리

소스코드

사용언어 : javascript

function solution(maps) {
    const n = maps.length;
    const m = maps[0].length;
    
    return BFS(maps, [0, 0], n, m);
}

const BFS = (graph, start, n, m) => {
    const visited = Array.from(Array(n), () => Array(m).fill(0));
    const dir = [[-1, 0], [0,1], [1,0], [0, -1]];

    let needVisit = []; // 탐색해야할 노드들. Queue로 사용할 배열

    needVisit.push(start); // 노드 탐색 시작
    visited[start[0]][start[1]] = 1;

    while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
        const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
        const [y, x] = [node[0], node[1]];

        if (y == (n-1) && x == (m-1)) return visited[y][x];
        for (const d of dir) {
            const [nY, nX] = [y + d[0], x + d[1]];
            
            if (nY < 0 || nY > n-1 || nX < 0 || nX > m-1) continue;
            if (graph[nY][nX] == 0) continue;
            
            // 방문하지 않았거나, 이미 방문했는데 현재 경로(위치)에서 갔을 때가 더 최단거리인 경우
            if (visited[nY][nX] == 0 || visited[nY][nX] > visited[y][x] + 1) {
                visited[nY][nX] = visited[y][x] + 1;
                needVisit.push([nY, nX]);
            }
        }
    }
    return -1;
};

2차원 배열

* Array.from(Array(n), () => Array(m).fill(0));

* n X m 배열을 0으로 채움

 

 

구조 분해 할당

* https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment 

* const [a, b] = [1, 2] 

* 우변의 값을 분해하여 좌변의 변수에 각각 할당할 수 있다

구조 분해 할당 - JavaScript | MDN

 

한줄평

BFS 오랜만에 풀었는데, 생각보다 쉽게 풀었다. 아직 뇌가 초기화 되지 않았나봄

 

 

참고 블로그

https://velog.io/@diveforme/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EC%97%90%EC%84%9C-...-%EC%9D%98%EB%AF%B8