[프로그래머스] [PCCP 모의고사 #2] 4번 - 보물 지도 JavaScript

혅·2025년 3월 3일

JavaScript

백준, 프로그래머스 -JavaScript-

목록 보기

202/215

문제

진수는 보물이 묻힌 장소와 함정이 표시된 보물 지도를 이용해 보물을 찾으려 합니다. 보물지도는 가로 길이가 n, 세로 길이가 m인 직사각형 모양입니다.

맨 왼쪽 아래 칸의 좌표를 (1, 1)으로, 맨 오른쪽 위 칸의 좌표를 (n, m)으로 나타냈을 때, 보물은 (n, m) 좌표에 묻혀있습니다. 또한, 일부 칸에는 함정이 있으며, 해당 칸으로는 지나갈 수 없습니다.

진수는 처음에 (1, 1) 좌표에서 출발해 보물이 있는 칸으로 이동하려 합니다. 이동할 때는 [상,하,좌,우]로 인접한 네 칸 중 한 칸으로 걸어서 이동합니다. 한 칸을 걸어서 이동하는 데 걸리는 시간은 1입니다.

진수는 보물이 위치한 칸으로 수월하게 이동하기 위해 신비로운 신발을 하나 준비했습니다. 이 신발을 신고 뛰면 한 번에 두 칸을 이동할 수 있으며, 함정이 있는 칸도 넘을 수 있습니다. 하지만, 이 신발은 한 번밖에 사용할 수 없습니다. 신비로운 신발을 사용하여 뛰어서 두 칸을 이동하는 시간도 1입니다.

이때 진수가 출발점에서 보물이 위치한 칸으로 이동하는데 필요한 최소 시간을 구해야 합니다.

예를 들어, 진수의 보물지도가 아래 그림과 같을 때, 진수가 걸어서 오른쪽으로 3칸, 걸어서 위쪽으로 3칸 이동하면 6의 시간에 보물이 위치한 칸으로 이동할 수 있습니다. 만약, 오른쪽으로 걸어서 1칸, 위쪽으로 걸어서 1칸, 신비로운 신발을 사용하여 위로 뛰어 2칸, 오른쪽으로 걸어서 2칸 이동한다면 총 5의 시간에 보물이 위치한 칸으로 이동할 수 있으며, 이보다 빠른 시간 내에 보물이 있는 위치에 도착할 수 없습니다.

진수의 보물지도가 표현하는 지역의 가로 길이를 나타내는 정수 n, 세로 길이를 나타내는 정수 m, 함정의 위치를 나타내는 2차원 정수 배열 hole이 주어졌을 때, 진수가 보물이 있는 칸으로 이동하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 단, 보물이 있는 칸으로 이동할 수 없다면, -1을 return 해야 합니다.

제한 사항

1 ≤ n, m ≤ 1,000

단, n * m이 3 이상인 경우만 입력으로 주어집니다.

1 ≤ hole의 길이 ≤ n * m - 2

hole[i]는 [a, b]의 형태이며, (a, b) 칸에 함정이 존재한다는 의미이며, 1 ≤ a ≤ n, 1 ≤ b ≤ m을 만족합니다.
같은 함정에 대한 정보가 중복해서 들어있지 않습니다.

(1, 1) 칸과 (n, m) 칸은 항상 함정이 없습니다.

예제 입력

n : 4
m : 4
hole : [[2, 3], [3, 3]]

예제 출력

내가 했던 풀이 방법

graph를 n×m 크기의 0으로 채워진 배열로 초기화한 뒤, hole 위치를 1로 체크해준다. (이때, hole은 1부터 시작하지만 graph는 0부터 시작하므로 0-based로 맞춰준다.)
queue에 [0, 0, 0, 0]을 넣어준다. 이는 [x, y, count, used]를 의미하며 x, y는 위치 값이고 count는 해당 위치까지 얼마나 걸렸는지를 의미한다. used는 점프를 사용했는지 안 했는지를 의미한다.
visited는 n×m 크기로 [false, false]가 채워지도록 초기화해준다. 이는 해당 위치의 점프를 한 상태로 방문을 했는지 점프를 하지 않은 상태로 방문을 했는지를 의미한다. (이때 점프를 한 상태는 해당 위치로 점프를 했다가 아닌, 점프를 한 상태에서 해당 위치에 도달했다를 의미한다.)
visited[0][0][0]을 true로 방문처리해주고 BFS를 진행한다. 만약 x, y가 n-1/m-1이라면 해당 count를 return 한다. 아직 도달하지 않았다면 상하좌우로 이동을 할 것이다. 상하좌우로 이동한 상태가 현재 used 상태로 방문하지 않았으며, hole이 아니라면 방문처리하고 queue에 넣어준다. 이때 count를 1 증가시킨 채로 넣어주어야 한다.
만약 used가 0이라면 (점프를 아직 하지 않았다면) 현재 위치(4번에서 이동한 위치 X) 상하좌우 방향으로 2칸 이동한 위치가 점프한 상태로 방문하지 않았으며, 도달할 위치가 hole이 아니라면 점프 상태로 해당 위치를 방문했음을 처리해주고, queue에 넣어준다. 점프도 count가 1회 증가하므로 count를 1 증가시켜준다.
BFS가 끝난 뒤에도 return 되지 않았다면 도달할 수 없는 것이므로 -1을 return 한다.

코드

function solution(n, m, hole) {
    const dx = [1, -1, 0, 0];
    const dy = [0, 0, 1, -1];

    const graph = Array.from({ length: n }, () => Array(m).fill(0));
    for (const [a, b] of hole) {
        graph[a - 1][b - 1] = 1;
    }

    const queue = [[0, 0, 0, 0]];
    const visited = Array.from({ length: n }, () => 
        Array.from({ length: m }, () => [false, false])
    );
    visited[0][0][0] = true;

    while (queue.length) {
        const [x, y, count, used] = queue.shift();

        if (x === n - 1 && y === m - 1) {
            return count;
        }

        for (let i = 0; i < 4; i++) {
            let nx = x + dx[i];
            let ny = y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny][used] && graph[nx][ny] === 0) {
                visited[nx][ny][used] = true;
                queue.push([nx, ny, count + 1, used]);
            }

            if (used === 0) { 
                let jumpX = nx + dx[i];
                let jumpY = ny + dy[i];

                if (jumpX >= 0 && jumpX < n && jumpY >= 0 && jumpY < m && !visited[jumpX][jumpY][1] && graph[jumpX][jumpY] === 0) {
                    visited[jumpX][jumpY][1] = true;
                    queue.push([jumpX, jumpY, count + 1, 1]);
                }
            }
        }
    }

    return -1;
}