[JS] 게임 맵 최단거리

 

 

난이도: Lv. 2

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

프로그래머스

 

 

알고리즘

1. 시작 위치 배열을 큐에 넣는다. 시작 위치 배열은 [행 번호, 열 번호, 지나온 칸의 개수] 로 이루어져 있다.

2. 큐에서 배열을 하나 뺴서 현재 위치가 목적지인지 확인한다.

3-1. 목적지면 시작 위치부터 목적지까지 몇 칸을 지나왔는지 반환한다.

3-2. 목적지가 아니라면 위아래, 양 옆으로 갈 수 있는지 확인하고 갈 수 있다면 그 위치의 배열을 큐에 삽입하고 그 위치를 방문했음을 표시한다.

4. 큐에 아무것도 없을 때까지 2와 3의 과정을 반복한다.

 

 

코드

function solution(maps) {
    const Queue = [[0, 0, 1]];

    while (Queue.length) {
        const currPos = Queue.shift();

        if (currPos[0] === maps.length - 1 && currPos[1] === maps[0].length - 1) { return currPos[2]; }

        const row = currPos[0];
        const col = currPos[1];
        const count = currPos[2] + 1;

        if (row - 1 >= 0 && maps[row - 1][col]) {
            maps[row - 1][col] = 0;
            Queue.push([row - 1, col, count]);
        }
        if (row + 1 <= maps.length - 1 && maps[row + 1][col]) {
            maps[row + 1][col] = 0;
            Queue.push([row + 1, col, count]);
        }
        if (col - 1 >= 0 && maps[row][col - 1]) {
            maps[row][col - 1] = 0;
            Queue.push([row, col - 1, count]);
        }
        if (col + 1 <= maps[0].length - 1 && maps[row][col + 1]) {
            maps[row][col + 1] = 0;
            Queue.push([row, col + 1, count]);
        }
    }

    return -1;
}

 

 

주저리

BFS 문제를 풀어본 적이 없어서 별생각 없이 DFS로 했다가 시간도 개박살 나고 정확도도 박살 나서 질문하기 보니까 최단거리 문제는 BFS로 풀어야 한다고 해서 BFS로 풀었다. 근데 온갖 여러 테스트 케이스를 넣어봐도 다 맞는데 정확도가 박살이 났다. 내가 BFS를 잘못하고 있는 건가 해서 한참 들여다봤는데 그냥 목적지의 행과 열을 바꿔 적은 거였다. 그러고 나서 생각해 보니 내가 돌려본 모든 테스트 케이스는 정사각형이었다. 그렇다 나의 잘못이었다. 그렇지만 열받는다.