백준 2178 미로 탐색

걍걍규·2023년 10월 12일

문제 설명

입출력 예시

문제 접근법

아주 기초적이고 간단한 BFS를 이용한 문제였고 문제를 보고 정리를 해보았다

시작점은 문제에선 (1,1)으로 나와있지만 (0,0)으로 생각하는게 이해하기 편했고 N, M도 마찬가지로 N-1, M-1로 생각했다
예시는 모두 시작점이 좌측 상단의 끝이고 도착점이 우측 하단의 끝이였다 즉 엣지케이스는 없으니 대충 하나 잡고 봐도 될 듯 했다
1이면 접근 가능 0이면 접근 불가능하다는 것 그리고 N, M은 도착점이 우측 하단의 끝이 아닐수도 있다는 점을 생각하였다
그럼 이제 BFS를 구현해서 문제를 풀어보자 !
여기까지 정리 하는데 5분이 걸렸다

const fs = require('fs');
const input = fs.readFileSync('example.txt', 'utf-8').trim().split('\n');

const [N, M] = input.shift().split(' ');

const graph = input.map((el) => el.split('').map((el2) => +el2));

const dirs = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

const visited = Array.from({ length: graph.length }, () =>
  Array.from({ length: graph[0].length }, () => false)
);
const cntGraph = Array.from({ length: graph.length }, () =>
  Array.from({ length: graph[0].length }, () => 0)
);

const bfs = (x, y) => {
  const queue = [];
  queue.push([x, y]);
  visited[x][y] = true;
  cntGraph[x][y] += 1;

  while (queue.length !== 0) {
    const [curX, curY] = queue.shift();
    for (const dir of dirs) {
      const [nextX, nextY] = [curX + dir[0], curY + dir[1]];
      if (
        nextX >= 0 &&
        nextY >= 0 &&
        nextX < graph.length &&
        nextY < graph[0].length &&
        visited[nextX][nextY] === false &&
        graph[nextX][nextY] === 1
      ) {
        visited[nextX][nextY] = true;
        queue.push([nextX, nextY]);
        cntGraph[nextX][nextY] = cntGraph[curX][curY] + 1;
      }
    }
  }
};

bfs(0, 0);

console.log(cntGraph[N - 1][M - 1]);