[ 백준 _ 2178 ] 미로탐색 ( BFS - 자바스크립트 )

문제

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

2178번: 미로 탐색

 

How to Solve ?

 

[1] BFS

 

DFS와는 다르게 BFS는 자신의 위치에서 가장 가까운 노드를 찾고, 이동하는 탐색 알고리즘이기에 "최단거리"를 구하는데 매우 유용한 알고리즘이다.

 

그래프와 관련된 문제를 풀면서, DFS를 더 많이 접하여서 BFS 문제 푸는데 시간이 꽤 많이 걸렸는데 다 풀고 나니까 어느정도는 이해가 된 느낌이 든다.

 

function BFS(x, y) {
  const queue = [x, y];

  while (queue.length) {
    visited[x][y] = 1;

    x = queue.shift();
    y = queue.shift();

    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];

      if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
        continue;
      }

      if (maze[nx][ny] === 1 && visited[nx][ny] === 0) {
        maze[nx][ny] = maze[x][y] + 1; // 이전 노드의 값에서 +1 한 값
        queue.push(nx, ny);
      }
    }
  }
}

function solution() {
  for (let row = 0; row < maze.length; row++) {
    for (let col = 0; col < maze[row].length; col++) {
      if (maze[row][col] === 1) { // 1인 시작점을 만나면
        BFS(row, col); // BFS 시작하고, break
        break;
      }
    }
  }
  console.log(maze[n - 1][m - 1]);
}

const dx = [-1, 1, 0, 0]; // 좌, 우
const dy = [0, 0, -1, 1]; // 상, 하

let [n, m] = [4, 6];

let maze = [
  [1, 0, 1, 1, 1, 1],
  [1, 0, 1, 0, 1, 0],
  [1, 0, 1, 0, 1, 1],
  [1, 1, 1, 0, 1, 1],
];

let visited = [
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
];

console.log(solution());

 [ 1, 0, 9, 10, 11, 12 ],
  [ 2, 0, 8, 0, 12, 0 ],
  [ 3, 0, 7, 0, 13, 14 ],
  [ 4, 5, 6, 0, 14, 15 ]