백준2178 - 미로 탐색

https://www.acmicpc.net/problem/2178

문제 파악

N×M 크기의 배열로 표현되는 미로가 있다.
1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸이다.
이때, (1,1)에서 출발하여 (N,M) 위치로 이동할 때 지나야하는 최소의 칸 수를 구하라.

예제 파악

입력값

4 6
101111
101010
101011
111011

첫째 줄의 두 정수는 각각 N과 M이다.

계산이 용이하게 (1,1) 위치를 (0,0)으로 생각한다.
코드 상 배열 또한 입력값을 거꾸로 생각한다.

111011(*2)
101011
101010
1(*1)01111

(1) 표시가 (0,0) 위치를, (2) 표시가 (N,M) 위치를 나타낸다.

먼저 큐를 선언해서 {x: 0, y: 0} 요소를 넣어준다.
(0,0) 위치에서 시작하여 인접한 칸의 값이 1일 경우, 큐에 인접한 칸의 위치({x: 0, y:1})를 집어 넣고 인접한 칸의 값을 +1 더해준다.
큐의 요소를 하나 삭제하고 인접 칸 4개를 탐색한다.

(N,M) 위치까지 탐색을 반복한다.

최소 15칸을 지나서 미로를 빠져나올 수 있다.

코드

function solution(n, m, arr) {
    // 시계 방향
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];

    let queue = [];
    queue.push({ x: 0, y: 0 });

    while (queue.length > 0) {
        const element = queue.shift();

        for (let i = 0; i < 4; i++) {
            const nextX = element.x + dx[i];
            const nextY = element.y + dy[i];

            // 범위 밖
            if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) {
                continue;
            }

            // 인접한 요소가 1일 때만 이동
            if (arr[nextX][nextY] !== 1) {
                continue;
            }

            arr[nextX][nextY] = arr[element.x][element.y] + 1;
            queue.push({ x: nextX, y: nextY });
        }
    }

    const answer = arr[n - 1][m - 1];
    console.log(answer);
}