프로그래머스 [Lv. 2] 게임 맵 최단거리 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(maps) {
    const n = maps.length;
    const m = maps[0].length;
    
    const er = n - 1;
    const ec = m - 1;
    
    const dr = [1, 0, -1, 0];
    const dc = [0, 1, 0, -1];
    
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < m;
    };
    
    let V = Array(n).fill().map(() => Array(m).fill().map(() => 0))
    
    const bfs = () => {
        const q = [[0, 0]];
        maps[0][0] = 0;
        while (q.length) {
            const [r, c] = q.shift();
            for (let d = 0; d < 4; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                if (isValid(nr, nc) && maps[nr][nc] == 1 && V[nr][nc] == 0) {
                    V[nr][nc] += V[r][c] + 1;
                    q.push([nr, nc])
                }
            }
        }
    }
    V[0][0] = 1;
    bfs();
    const minLen = V[er][ec];
    const answer = minLen ? minLen : -1;
    return answer;
}

풀이 방법

1. visited 배열을 만들었는데 안 만들어도 풀 수 있다.
2. 1인 길을 따라간다.
3. 길을 따라가면서 거리를 누적한다.
4. 최적 경로가 0이라면 도달 못했으므로 -1

느낀점

• bfs와 dfs의 차이를 알면 풀기 쉬운 문제