[백준 알고리즘] Node.js 2178. 미로 탐색

1. 문제

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

2178번: 미로 탐색

 

2. 풀이

1) 최단거리를 구하는 문제이기에 BFS 사용!

2) [1,1] 부터 [N,M] 까지의 최단거리를 구하는 문제이다. 배열로 만들면 마지막에 답을 구할 때 각각 1씩 빼서 보여줘야한다.

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N,M]= inputs.shift().split(' ').map(v => +v);
const visited = Array.from({length : N}, () => new Array(M).fill(0));
const graph = inputs.map(v => v.split('').map(vv=> +vv));

const bfs = (x,y) => {
  const queue = [[x,y]];
  visited[x][y] = 1;

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

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

    for(let i = 0; i < 4; i++){
      const nx = x + dx[i];
      const ny = y + dy[i];
  
      if(nx >= 0 && ny >= 0 && nx < N && ny < M){
        if(graph[nx][ny] && !visited[nx][ny]){
          visited[nx][ny] = visited[x][y] + 1;
          queue.push([nx,ny])
        }
      }
    }
  }
}

bfs(0,0);
console.log(visited[N-1][M-1])

 

3. 정리

- 처음엔 BFS 함수 안에 매개변수로 진행을 했었다. 그랬더니 모든 경로를 다 통과한 값을 리턴해줌 ㅠㅠㅠㅠ

그래서 새로운 방문경로 배열을 만들고 방문했던 곳에 누적하여 값을 넣어주었다.

- 백준에서 그래도 몇문제 푸니까 감은 잡았는데....... 부족하다! 화이팅!