문제 설명 및 링크

https://programmers.co.kr/learn/courses/30/lessons/1844?language=javascript

나의 풀이

처음에는 재귀를 사용하여 최단 거리를 구하려고 했으나, 이상하게 자꾸 정확도 테스트 18, 19 번에서 자꾸 틀렸다고 나오더라;;;

뭘까... 효율성은 그렇다 쳐도 이론상 정확도는 틀릴 것 같진 않은데...

뭐 뭔가 놓친 사례가 있겠지. 어쨌든 효율성까지 실패했으니 재귀 대신 que 를 이용해서 최단 거리를 구하기로 했다.

• targets (Array) 에 시작 좌표 추가 (x: 0, y: 0)
• targets 에 좌표가 하나도 없을때까지 while 문 루프
  • 조건에 따라 현재 좌표의 left, right, up, down 방향 다음 좌표의 coast 증가하면서 targets 에 다음 좌표 추가

근데 개인적으로 효율성이 크게 차이가 나지 않거나 루프 횟수 한계가 명확하다면, 재귀든 que 든 코드가 깔끔한게 더 좋은 것 같음.

코드

모든 프로그래머스 문제 관련 코드들은 GitHub 링크 에 있음.

function solution(maps) {
    const N = maps.length;
    const M = maps[0].length;
    const targets = [{x: 0, y: 0}];

    while (targets.length > 0) {
        const {x, y} = targets.shift();
        const coast = maps[y][x];

        if (maps[N - 1][M - 1] !== 1 && coast >= maps[N - 1][M - 1]) {
            continue;
        }

        // left
        if (x > 0 && maps[y][x - 1] !== 0) {
            if (maps[y][x - 1] === 1 || maps[y][x - 1] > coast + 1) {
                maps[y][x - 1] = coast + 1;
                targets.push({x: x - 1, y});
            }
        }

        // right
        if (x < M - 1 && maps[y][x + 1] !== 0) {
            if (maps[y][x + 1] === 1 || maps[y][x + 1] > coast + 1) {
                maps[y][x + 1] = coast + 1;
                targets.push({x: x + 1, y});
            }
        }

        // up
        if (y > 0 && maps[y - 1][x] !== 0) {
            if (maps[y - 1][x] === 1 || maps[y - 1][x] > coast + 1) {
                maps[y - 1][x] = coast + 1;
                targets.push({x, y: y - 1});
            }
        }

        // down
        if (y < N - 1 && maps[y + 1][x] !== 0) {
            if (maps[y + 1][x] === 1 || maps[y + 1][x] > coast + 1) {
                maps[y + 1][x] = coast + 1;
                targets.push({x, y: y + 1});
            }
        }
    }

    return maps[N - 1][M - 1] === 1 ? -1 : maps[N - 1][M - 1];
}