[JS] 백준 2178번 미로 탐색

Contents

• 문제 링크
• 풀이 전략
• 코드 

---

문제 링크

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

풀이 전략

이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오

코드 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

solution(input);

function solution(arr) {
    const [n, m] = arr.shift().split(" ").map(Number);
    const dp = Array.from({ length: n }, () => Array(m).fill(0));
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];

    arr = arr.map((v) => v.split("").map(Number));
    bfs(0, 0);

    function bfs(fx, fy) {
        const queue = [];
        queue.push([fx, fy]);
        dp[fx][fy] = 1;

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

            for (let i = 0; i < 4; i++) {
                const [nx, ny] = [x + dx[i], y + dy[i]];
                if (
                    0 <= nx &&
                    nx < n &&
                    0 <= ny &&
                    ny < m &&
                    arr[nx][ny] &&
                    !dp[nx][ny]
                ) {
                    dp[nx][ny] = dp[x][y] + 1;
                    queue.push([nx, ny]);
                }
            }
        }

        console.log(dp[n - 1][m - 1]);
    }
}

 

회고

처음엔 dfs에서 시간을 줄이는 방식을 이용했는데 이래도 시간 초과가 발생하여서 bfs를 이용해서 구현하였다. dfs와 달리 bfs는 각 인접 노드를 레벨(깊이) 별로 탐색하기 때문에 시간이 단축될 수 밖에 없다.

여기서 헷갈리는 점은 이 문제에서 각 정점까지 걸리는 거리를 이차원 배열에 저장하는데 이거는 동적 프로그래밍(Dynamic Programming)이 아닌지 맞는지 확실히 모르겠다. 일단 내 생각엔 맞다고 생각하여 네이밍을 했는데 혹시 아시는 분은 댓글 남겨 주시길.... 

bfs를 사용해야한다는 점을 깨달았다면 구현자체는 어렵지 않은 문제였다. 

 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

solution(input);

function solution(arr) {
    const [n, m] = arr.shift().split(" ").map(Number);
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    let min = Number.MAX_SAFE_INTEGER;

    arr = arr.map((v) => v.split("").map(Number));

    arr[0][0] = 0;
    dfs(0, 0, 1);

    function dfs(x, y, cnt) {
        if (cnt >= min) return;
        if (x === n - 1 && y === m - 1) {
            min = Math.min(min, cnt);
        } else {
            for (let i = 0; i < 4; i++) {
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (0 <= nx && nx < n && 0 <= ny && ny < m && arr[nx][ny]) {
                    arr[nx][ny] = 0;
                    dfs(nx, ny, cnt + 1);
                    arr[nx][ny] = 1;
                }
            }
        }
    }

    console.log(min);
}

dfs로 시도하였을 때 제출한 코드. 

---

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)