[javascript] 백준 2178번 미로 탐색

문제보기

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input[0].split(" ").map((value) => +value);
const maze = input
    .slice(1)
    .map((item) => item.split("").map((value) => +value));
const direction = [
    [-1, 0],
    [0, -1],
    [1, 0],
    [0, 1],
];

const BFS = (row, col) => {
    let queue = [[row, col]];
    let visited = new Array(N).fill(0).map(() => new Array(M).fill(0));
    visited[row][col] = 1;
    while (queue.length) {
        let [x, y] = queue.shift();
        for (let i = 0; i < 4; i++) {
            let [dx, dy] = [x + direction[i][0], y + direction[i][1]];
            if (dx < 0 || dy < 0 || dx >= N || dy >= M) continue;
            if (maze[dx][dy] && !visited[dx][dy]) {
                visited[dx][dy] = visited[x][y] + 1;
                queue.push([dx, dy]);
                if (dx === N - 1 && dy === M - 1) {
                    return visited[dx][dy];
                }
            }
        }
    }
};

console.log(BFS(0, 0));

최단경로 탐색이므로 bfs가 유리하다고 판단했다
왜냐하면 dfs가 속도는 더 빠를수 있어도 최단경로를 보장해주지 못하기 때문이다

풀이

시작지점 0,0의 값을 1로 시작한다
해당 좌표에서 동서남북을 확인하여 길이 있고 방문한적이 없는곳이면
현재좌표 값에서 +1한 값을 넣어준다.
bfs 실행중 목표 좌표에 도착하면 해당 좌표의 값을 반환한다.