[백준] 미로 탐색 문제 자바스크립트 풀이 - BFS

> 문제 바로가기

2178번: 미로 탐색

 

 

1. 접근 방법

 

(1) 입력받은 n, m, graph 잘라서 준비해두기

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = input.shift().split(" ");
let graph = input.map(arr => arr.split("").map(x => +x));

 

(2) n, m, graph 인자로 받는 BFS 함수 만들기 

(3) 현재 노드에서 오른쪽, 아래, 왼쪽, 위 방향으로 가는 x, y 좌표값을 만들어줌.

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

 

(4) 빈 queue 만들어 주고, 거기에 첫 좌표 넣어주기.

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

 

(5) while문으로 큐 안에 노드가 없어질 때까지, 각 노드에 대해 for문으로 조건에 맞는 다음 노드가 있으면 다음 노드에 1을 더해줌

    while (queue.length) {
        const target = queue.shift();
        for (let i = 0; i < 4; i++) {
            const nextX = target.x + dx[i];
            const nextY = target.y + dy[i];
            
            if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) {
                continue;
            }
            
            if (arr[nextX][nextY] !== 1) {
                continue;
            }
            
            arr[nextX][nextY] = arr[target.x][target.y] + 1;
            queue.push({x: nextX, y: nextY});
        }
    }

 

(6) 마지막 좌표 값 리턴해주고 콘솔에 답 찍기

 

2. 전체 해답 

 

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = input.shift().split(" ");
let graph = input.map(arr => arr.split("").map(x => +x));

const BFS = (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) {
        const target = queue.shift();
        for (let i = 0; i < 4; i++) {
            const nextX = target.x + dx[i];
            const nextY = target.y + dy[i];
            
            if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) {
                continue;
            }
            
            if (arr[nextX][nextY] !== 1) {
                continue;
            }
            
            arr[nextX][nextY] = arr[target.x][target.y] + 1;
            queue.push({x: nextX, y: nextY});
        }
    }
    return arr[n-1][m-1];
}

const answer = BFS(n, m, graph)
console.log(answer)

 

풀이가 다소 복잡해 보이지만 내가 공부한 그래프 BFS 풀이의 정석대로 해결했다. 예쁘게 코드를 정리하는 것은 다음 레벨부터 해 볼 것이다.