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

1. 문제

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

프로그래머스

2. 코드

알고린이 울어유,,, 이게 어떻게 레벨2야!?!! 꼭 복기해야겠다..

이 문제는 bfs로 풀어야겠다고 생각만하고 풀이 과정은 못찾은 문제..^^ 근데 익숙해지면 이런 류의 최단거리 문제는 잘 풀 수 있을 것 같기도하고(허언증)! bfs는 큐 또는 연결리스트로 구현한다는 것도 잊지말자. 로직 자체는 막 어려워서 이해가 안되는 건 아닌데, 처음부터 혼자 짜기에는 어려운 것 같다.

function solution(maps) {
    const n = maps.length; // 세로
    const m = maps[0].length; // 가로
    let answer = -1;
    let visited = Array.from(Array(n), () => Array(m).fill(false));

    // BFS 를 하기 위한 queue, 초기 값 저장 => [x좌표,y좌표,움직인 횟수]
    let queue = [[0, 0, 1]];
    // x, y 가 움직일 배열을 저장함 (상, 우, 하, 좌)
    const moveX = [-1, 0, 1, 0]; // 좌 우
    const moveY = [0, 1, 0, -1]; // 하 상

    const visit = (x, y, count) => {
        visited[x][y] = true;

        // 현재 x, y 위치에서 상, 하, 좌, 우 로 이동할 반복문
        for (let i = 0; i < moveX.length; i++) {
            // 움직일 좌표
            const movedX = x + moveX[i];
            const movedY = y + moveY[i];

            // 만약, movedX, movedY 가 배열의 범위 안에 있고, 그 값 위치가 아직 방문하지 않았고,
            // 그 위치를 방문할 수 있다면
            if (movedX >= 0 && movedX < m && movedY >= 0 && movedY < n 
            && !visited[movedX][movedY] && maps[movedX][movedY] === 1) {
                // queue 에 그 값을 넣음
                // 왠만하면 ++보단 +1 쓰기
                queue.push([movedX, movedY, count+1]);
            }
        }
    }

    // BFS
    // 큐에 새로운 배열이 들어가지 않으면, 즉 길이 막혀있어 갈 곳이 없다면
    // queue.length가 0이 되며 while 문 탈출
    while (queue.length) {
        // 일단 queue 에 있는 값을 꺼냄
        const now = queue.shift();
        console.log(now)

        // 만약 꺼낸 값이 정답 (도착지) 이면
        if (now[0] === m - 1 && now[1] === n - 1) {
            // answer 에 답을 저장함 (now[2] 는 이동 거리)
            answer = now[2];
            break;
        }

        // 만약 꺼낸 값이 방문하지 않은 값이라면
        if (!visited[now[0]][now[1]]) {
            // 방문
            visit(now[0], now[1], now[2])
        }
    }
    
    return answer;
}

이게 예제의 방문 순서이다!

 

+ 복기하기 정말 정말 싫었던 문제....ㅎㅎ 한시간은 붙들었나보다

복기

4/14