백준, 2178 미로 탐색 javascript

백준,2178 미로 탐색

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

👨‍💻 문제 풀이

• bfs로 문제를 풀 수 있다.
• bfs는 가능한 방향의 끝까지 탐색한다.
• 해당 좌표에 몇번째로 도달했는지 판단하는 객체를 만들어 사용하면, 해당 객체를 통해서 끝까지 가는 최단경로를 알 수 있다.

💻 제출한 코드

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


const [N, M] = input.shift().split(' ').map(Number);
const map = input.map((row) => row.split('').map(Number));


function bfs(x,y) {
    const queue = [[x,y]];
    const result = [];
    const visisted = { };
    visisted[[x,y]] = 1;
    let dx = [0, 0, -1, 1];
    let dy = [-1, 1, 0, 0];
	// vistied를 몇번째 방문했는지 판단하는 객체로 활용한다.
    while(queue.length) {
        for(let i=0; i<queue.length; i++) {
            let coord = queue.shift();
            result.push(coord);
            for(let j=0; j<4; j++) {
                let nx = coord[0] + dx[j];
                let ny = coord[1] + dy[j];

                if( nx >= 0 &&
                    ny >= 0 &&
                    nx < N &&
                    ny < M &&
                    !visisted[[nx,ny]] &&
                    map[nx][ny] === 1) {
                        visisted[[nx,ny]] = visisted[coord]+1;
                  // 해당 좌표에 도달할때마다 visited 객체값을 증가시켜준다.
                        queue.push([nx,ny]);
                    }
            }
        }
    }
    return visisted[[N-1,M-1]];
  // N, M 좌표에 도달했을 때 visited객체에 담겨져 있는 값을 리턴한다.
}

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

이번 문제를 풀면서,

• 이 문제는 숨바꼭질 문제와 비슷하다.
• 숨바꼭질 문제도 visited 객체를 다른 방식으로 활용하는데,
• 이 문제를 풀고 숨바꼭질 문제를 풀었으면 더 쉽게 풀 수 있었을 것 같다.
• BFS의 여러 문제를 풀면서 이렇게도 활용될 수 있구나에 감탄하고 있다.