[프로그래머스] JavaScript Lv2 - 게임 맵 최단거리(1844)

개요

문제 이름: 게임 맵 최단거리 (1844)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844
플랫폼: 프로그래머스
알고리즘 분류: 깊이/너비 우선 탐색(DFS/BFS)
소요 시간: 24시간...

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 전형적인 최단 경로 찾기 문제로, 너비 우선 탐색(BFS: Breadth-First Search) 알고리즘을 사용하여 해결할 수 있습니다. BFS는 그래프나 트리 구조에서 가장 가까운 노드부터 탐색하는 방법으로, 최단 경로를 찾는 데 적합합니다.

 

이 문제에서 게임 맵은 2차원 그래프로 표현할 수 있습니다. 각 칸은 그래프의 노드이며, 상하좌우로 인접한 칸들 사이에는 엣지가 있다고 볼 수 있습니다. 시작 위치에서부터 BFS를 수행하여 도착 위치까지의 최단 경로를 찾으면 됩니다.

문제 요구 사항

• 시작점(1, 1)에서 도착점(n, m)까지의 최단 거리를 찾아야 합니다.
• 이동은 상, 하, 좌, 우로만 가능합니다.
• 벽(0)으로 표시된 곳은 지나갈 수 없습니다.
• 도착점에 도달할 수 없다면 -1을 반환해야 합니다.

 

문제 접근 방식

1. 시작 위치 (0, 0)을 큐에 넣고 시작합니다. 이때 거리는 1입니다.
2. 큐에서 현재 위치를 꺼내고, 상하좌우로 이동 가능한 위치를 검사합니다.
3. 이동 가능한 위치라면 (맵 범위 내에 있고, 벽이 아니며, 아직 방문하지 않은 경우) 해당 위치를 큐에 넣고 거리를 기록합니다.
4. 큐가 빌 때까지 2~3번 과정을 반복합니다.
5. 도착점에 도달하면 그때의 거리를 반환합니다.
6. 큐가 비어질 때까지 도착점에 도달하지 못하면 -1을 반환합니다.

 

시도

1차 시도 (실패)

function solution(maps) {
    const n = maps.length, m = maps[0].length;
    let x = 0, y = 0, dist = 1;  // 시작 위치와 거리
    while (x < n - 1 || y < m - 1) {  // 목적지에 도달할 때까지
        if (y < m - 1 && maps[x][y + 1]) y++;  // 오른쪽으로 이동 가능하면 이동
        else if (x < n - 1 && maps[x + 1][y]) x++;  // 아래로 이동 가능하면 이동
        else return -1;  // 더 이상 이동할 수 없으면 실패
        dist++;  // 거리 증가
    }
    return dist;  // 총 이동 거리 반환
}

이 코드는 그리디(Greedy) 접근 방식을 사용하여 문제를 해결하려고 시도했습니다. 현재 위치에서 오른쪽 또는 아래로 이동할 수 있다면 이동하고, 더 이상 이동할 수 없다면 -1을 반환합니다.

하지만 이 방법은 최단 경로를 보장하지 않습니다. 예를 들어, 오른쪽이나 아래로 이동하는 것이 최선이 아닌 경우가 있을 수 있습니다. 따라서 이 코드로는 문제를 올바르게 해결할 수 없습니다.

 

• 항상 오른쪽이나 아래쪽으로만 이동하려고 합니다. 이는 최단 경로가 왼쪽이나 위쪽으로 이동해야 하는 경우를 고려하지 않습니다.
• 한 번 선택한 경로에서 벽을 만나면 바로 실패로 판단합니다. 다른 가능한 경로를 탐색하지 않습니다.

더 정확하게 설명하자면 위와 같은 문제점이 있습니다.

 

시간 복잡도: O(n+m), 여기서 n과 m은 맵의 행과 열의 수입니다.

공간 복잡도: O(1), 추가적인 공간을 사용하지 않습니다.

 

2차 시도 (실패)

function solution(maps) {
    const n = maps.length;
    const m = maps[0].length;
    const queue = [[0, 0, 1]];  // [row, col, distance]
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];  // 상하좌우 이동 방향
    while (queue.length > 0) {
        const [row, col, dist] = queue.shift();  // 큐에서 현재 위치 추출
        if (row === n - 1 && col === m - 1) {  // 목적지 도달
            return dist;
        }
        for (const [dr, dc] of directions) {  // 네 방향으로 이동 시도
            const newRow = row + dr;
            const newCol = col + dc;
            // 새 위치가 유효하고 벽이 아니라면
            if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && maps[newRow][newCol] === 1) {
                queue.push([newRow, newCol, dist + 1]);  // 큐에 새 위치 추가
                maps[newRow][newCol] = 0;  // 방문 표시 (이 부분이 비효율적일 수 있음)
            }
        }
    }
    return -1;  // 목적지에 도달할 수 없는 경우
}

이 코드는 BFS를 사용하여 문제를 해결하려고 시도했습니다. 시작 위치부터 큐에 넣고, 큐에서 위치를 하나씩 꺼내면서 상하-좌우로 이동합니다. 이동할 수 있는 위치는 큐에 넣고, 방문한 위치는 벽(0)으로 표시합니다.

 

하지만 이 코드에는 효율성 문제가 있습니다.

 

방문한 위치를 벽으로 표시하는 대신 별도의 방문 배열을 사용하는 것이 더 효율적입니다. queue.shift()를 사용하여 큐의 앞에서 요소를 제거하는 것은 O(n) 시간이 걸립니다. 큐가 크면 이 연산이 매우 비효율적일 수 있습니다. 또한 큐에 방문한 위치를 표시할 때마다 새로운 배열을 생성하므로 불필요한 메모리 할당이 발생합니다.

결국, 이 코드는 시간 초과로 인해 일부 테스트 케이스를 통과하지 못했습니다.

 

시간 복잡도: 최악의 경우 O(n * m * (n + m)), 여기서 n과 m은 맵의 행과 열의 수입니다.

공간 복잡도: O(n * m), 최악의 경우 모든 위치를 큐에 넣을 수 있습니다.

 

3차 시도 (성공)

function solution(maps) {
    const n = maps.length;
    const m = maps[0].length;
    const queue = [[0, 0]];  // 시작 위치
    const visited = Array.from({ length: n }, () => new Array(m).fill(0));  // 방문 및 거리 기록 배열
    visited[0][0] = 1;  // 시작 위치 방문 표시 및 거리 1로 초기화
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];  // 상하좌우 이동 방향
    let queueIndex = 0;  // 큐의 현재 인덱스
    while (queueIndex < queue.length) {
        const [row, col] = queue[queueIndex++];  // 현재 위치
        const dist = visited[row][col];  // 현재까지의 거리
        if (row === n - 1 && col === m - 1) {  // 목적지 도달
            return dist;
        }
        for (const [dr, dc] of directions) {  // 네 방향으로 이동 시도
            const newRow = row + dr;
            const newCol = col + dc;
            // 새 위치가 유효하고, 벽이 아니며, 아직 방문하지 않았다면
            if (
                newRow >= 0 && newRow < n &&
                newCol >= 0 && newCol < m &&
                maps[newRow][newCol] === 1 &&
                !visited[newRow][newCol]
            ) {
                queue.push([newRow, newCol]);  // 큐에 새 위치 추가
                visited[newRow][newCol] = dist + 1;  // 새 위치의 거리 기록
            }
        }
    }
    return -1;  // 목적지에 도달할 수 없는 경우
}

이 코드는 BFS를 사용하여 문제를 올바르게 해결합니다. 시작 위치부터 큐에 넣고, 큐에서 위치를 하나씩 꺼내면서 상하-좌우로 이동합니다. 이동할 수 있는 위치는 큐에 넣고, 해당 위치까지의 거리를 visited 배열에 기록합니다. 참고로 shift() 대신 인덱스를 사용하여 큐를 관리합니다. 이로 인해 큐 조작의 시간 복잡도가 O(1)로 개선됐습니다.

 

visited 배열은 각 위치의 방문 여부와 시작 위치로부터의 거리를 저장합니다. 이는 원본 맵을 수정하지 않고도 효율적으로 방문 정보를 저장할 수 있게 합니다.  시작 위치의 거리는 1로 초기화하고, 이동할 때마다 거리를 1씩 증가시킵니다.

 

큐에서 위치를 꺼낼 때는 queueIndex를 사용하여 큐의 앞쪽부터 차례대로 꺼냅니다. 이를 통해 불필요한 배열 생성(탐색)을 피할 수 있습니다. 목적지에 도달하면 해당 위치까지의 거리를 반환하고, 큐가 빌 때까지 도달하지 못하면 -1을 반환합니다.

 

시간 복잡도: O(n * m), 각 위치를 최대 한 번씩만 방문합니다.

공간 복잡도: O(n * m), visited 배열과 큐를 위한 공간이 필요합니다.

 

사용된 메서드

• Array.from(): 주어진 길이와 초기화 함수를 사용하여 새로운 배열을 생성합니다. 여기서는 2차원 배열을 초기화하는 데 사용되었습니다.
• Array.fill(): 배열의 모든 요소를 지정된 값으로 채웁니다.
• Array.push(): 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새 길이를 반환합니다.