문제

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

풀이

0과 1로 이루어진 미로에서 한칸씩 이동하며 목표 거리까지 도달하는 데에 소요되는 최소 거리를 구하는 문제다. 최단 거리를 찾아야하기 때문에 bfs를 활용해서 풀이했다.

// 2178 미로탐험

const [N, M, ...rows] = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(/\s+/);
// console.log(inputs);

// console.log(rows);

const dy = [1, -1, 0, 0];
const dx = [0, 0, 1, -1];

// Solution body
function solution() {
    const n = parseInt(N);
    const m = parseInt(M);

    const mp = [];
    // console.log(visited);
    // init maze
    for (const row of rows) {
        mp.push(Array.from(row).map((el) => parseInt(el)));
    }

    // console.log(mp);

    const bfs = () => {
        let queue = [[0, 0]];
        while (queue.length >= 1) {
            const [cy, cx] = queue.shift();
            if (cy == n - 1 && cx == m - 1) {
                console.log(mp[cy][cx]);
                return;
            }

            for (let i = 0; i < 4; i++) {
                const ny = cy + dy[i];
                const nx = cx + dx[i];

                // 이동 가능한 좌표
                if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                    if (mp[ny][nx] === 1) {
                        queue.push([ny, nx]);
                        mp[ny][nx] += mp[cy][cx];
                    }
                }
            }
        }
    };

    bfs();
}

// Execute
solution();

회고

파이썬으로 풀었던 것을 js로 바꿔보는 것만으로도 꽤나 도움이 되었다. 가장 기본적인 문제지만 이를 응용한 문제가 많으니 종종 연습해두는 것도 좋겠다.