프로그래머스 LEVEL 2(게임 맵 최단거리)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2022-09-09

  • 해결 방법 :
    • 목적지까지의 최단 거리를 찾는 것이므로 bfs 사용
    • visited 배열을 따로 만들어 방문 여부 확인
    • [0, 0]부터 시작하여 각 동, 서, 남, 북의 방향으로 이동 가능하며, 이미 방문한 곳이 아니며, 막혀있는 곳이 아닐 때 큐에 push() 및 거리 1씩 증가
  • 회고 :
    • 2차원 배열의 참조(maps.length, maps[0].length) 순서

  • 코드

    function solution(maps) {
    const visited = Array.from(Array(maps.length), () => Array(maps[0].length).fill(0));
    const moveX = [1, -1, 0, 0];
    const moveY = [0, 0, 1, -1];

    const bfs = () => {
        const q = [[0, 0]];

        while(q.length) {
            const curPos = q.shift();
            const curX = curPos[0];
            const curY = curPos[1];
                
            if (!visited[curX][curY]) {
                visited[curX][curY] = 1;

                for (let i = 0; i < 4; i++) {
                    const nextX = curX + moveX[i];
                    const nextY = curY + moveY[i];

                    if (nextX < 0 || nextX >= maps.length || nextY < 0 || nextY >= maps[0].length) continue;
                    if (maps[nextX][nextY] && !visited[nextX][nextY]) {
                        q.push([nextX, nextY]);
                        maps[nextX][nextY] = maps[curX][curY] + 1;
                    }
                }
            }
        }
    }
        
    bfs();
        
    return maps[maps.length - 1][maps[0].length - 1] === 1 ? -1 : maps[maps.length - 1][maps[0].length - 1];
}
  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges