미로 탐색에서 최단 거리를 구할 때는 BFS가 정석.

BFS는 시작점에서 가까운 칸부터 차례대로 탐색하기 때문에, 처음으로 목적지에 도달했을 때의 거리가 곧 최단 거리

1. 큐(Queue)를 사용

DFS가 재귀를 사용한다면, BFS는 큐(Queue)를 사용합니다. JavaScript에서는 보통 배열의 push()와 shift()를 이용해 구현합니다.

• queue = [[0, 0]] (시작 좌표 삽입)
• 큐가 빌 때까지 while문을 돌립니다.
• 큐에서 하나를 꺼내(shift) 사방을 탐색하고, 갈 수 있는 곳을 다시 큐에 넣습니다.

2. 거리를 기록(Distance)

단순히 방문했는지만 체크하는 게 아니라, 시작점으로부터 몇 번째 칸인지 maze 배열에 직접 기록하는 것이 편합니다.

• 다음 칸의 값 = 현재 칸의 값 + 1
• maze[nx][ny] = maze[x][y] + 1

---

const fs = require("fs");

const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");
//input에 각 줄이 배열 자료형으로 담기므로 각 줄에 접근하려면 인덱싱으로 접근

const [N, M] = input[0].split(" ").map(Number);
const maze = input.slice(1).map((line) => line.split("").map(Number));

//오, 아, 왼, 위
const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];

cnt = 0;

function bfs(startX, startY) {
  // queue = [[0, 0]] (시작 좌표 삽입)
  const queue = [[startX, startY]];
  // queue가 빌 때까지 while문 돌리기
  while (queue.length > 0) {
    // 큐에서 하나를 꺼내(shift) 사방을 탐색하고, 갈 수 있는 곳을 다시 큐에 넣습니다.
    const [x, y] = queue.shift();
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      // 1. maze범위에 있고
      if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
        // 2. 갈 수 있는 길(1)인 경우만 탐색
        if (maze[nx][ny] === 1) {
          // 3. 현재까지의 거리 + 1을 다음 칸에 저장
          maze[nx][ny] = maze[x][y] + 1;
          queue.push([nx, ny]);
        }
      }
    }
  } // 목적지 좌표의 값을 반환
  return maze[N - 1][M - 1];
}

console.log(bfs(0, 0));
).toString().trim().split("\n");
//input에 각 줄이 배열 자료형으로 담기므로 각 줄에 접근하려면 인덱싱으로 접근

const [N, M] = input[0].split(" ").map(Number);
const maze = input.slice(1).map((line) => line.split("").map(Number));

//오, 아, 왼, 위
dx = [0, 1, 0, -1];
dy = [1, 0, -1, 0];

cnt = 0;

function bfs(startX, startY) {
  // queue = [[0, 0]] (시작 좌표 삽입)
  const queue = [[startX, startY]];
  // queue가 빌 때까지 while문 돌리기
  while (queue.length > 0) {
    // 큐에서 하나를 꺼내(shift) 사방을 탐색하고, 갈 수 있는 곳을 다시 큐에 넣습니다.
    const [x, y] = queue.shift();
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      // 1. maze범위에 있고
      if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
        // 2. 갈 수 있는 길(1)인 경우만 탐색
        if (maze[nx][ny] === 1) {
          // 3. 현재까지의 거리 + 1을 다음 칸에 저장
          maze[nx][ny] = maze[x][y] + 1;
          queue.push([nx, ny]);
          console.log(maze);
        }
      }
    }
  } // 목적지 좌표의 값을 반환
  return maze[N - 1][M - 1];
}

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

출력예시

Desktop/Coding_Test/2178.js"
[
  [ 1, 0, 1, 1, 1, 1 ],
  [ 2, 0, 1, 0, 1, 0 ],
  [ 1, 0, 1, 0, 1, 1 ],
  [ 1, 1, 1, 0, 1, 1 ]
]
[
  [ 1, 0, 1, 1, 1, 1 ],
  [ 2, 0, 1, 0, 1, 0 ],
  [ 3, 0, 1, 0, 1, 1 ],
  [ 1, 1, 1, 0, 1, 1 ]
]
[
  [ 3, 0, 1, 1, 1, 1 ],
  [ 2, 0, 1, 0, 1, 0 ],
  [ 3, 0, 1, 0, 1, 1 ],
  [ 1, 1, 1, 0, 1, 1 ]
]
[
  [ 3, 0, 1, 1, 1, 1 ],
  [ 2, 0, 1, 0, 1, 0 ],
  [ 3, 0, 1, 0, 1, 1 ],
  [ 4, 1, 1, 0, 1, 1 ]
]
[
  [ 3, 0, 1, 1, 1, 1 ],
  [ 2, 0, 1, 0, 1, 0 ],
  [ 3, 0, 1, 0, 1, 1 ],
  [ 4, 5, 1, 0, 1, 1 ]
]
[
  [ 3, 0, 1, 1, 1, 1 ],
  [ 2, 0, 1, 0, 1, 0 ],
  [ 3, 0, 1, 0, 1, 1 ],
  [ 4, 5, 6, 0, 1, 1 ]
]
[
  [ 3, 0, 1, 1, 1, 1 ],
  [ 2, 0, 1, 0, 1, 0 ],
  [ 3, 0, 7, 0, 1, 1 ],
  [ 4, 5, 6, 0, 1, 1 ]
]
[
  [ 3, 0, 1, 1, 1, 1 ],
  [ 2, 0, 8, 0, 1, 0 ],
  [ 3, 0, 7, 0, 1, 1 ],
  [ 4, 5, 6, 0, 1, 1 ]
]
[
  [ 3, 0, 9, 1, 1, 1 ],
  [ 2, 0, 8, 0, 1, 0 ],
  [ 3, 0, 7, 0, 1, 1 ],
  [ 4, 5, 6, 0, 1, 1 ]
]
[
  [ 3, 0, 9, 10, 1, 1 ],
  [ 2, 0, 8, 0, 1, 0 ],
  [ 3, 0, 7, 0, 1, 1 ],
  [ 4, 5, 6, 0, 1, 1 ]
]
[
  [ 3, 0, 9, 10, 11, 1 ],
  [ 2, 0, 8, 0, 1, 0 ],
  [ 3, 0, 7, 0, 1, 1 ],
  [ 4, 5, 6, 0, 1, 1 ]
]
[
  [ 3, 0, 9, 10, 11, 12 ],
  [ 2, 0, 8, 0, 1, 0 ],
  [ 3, 0, 7, 0, 1, 1 ],
  [ 4, 5, 6, 0, 1, 1 ]
]
[
  [ 3, 0, 9, 10, 11, 12 ],
  [ 2, 0, 8, 0, 12, 0 ],
  [ 3, 0, 7, 0, 1, 1 ],
  [ 4, 5, 6, 0, 1, 1 ]
]
[
  [ 3, 0, 9, 10, 11, 12 ],
  [ 2, 0, 8, 0, 12, 0 ],
  [ 3, 0, 7, 0, 13, 1 ],
  [ 4, 5, 6, 0, 1, 1 ]
]
[
  [ 3, 0, 9, 10, 11, 12 ],
  [ 2, 0, 8, 0, 12, 0 ],
  [ 3, 0, 7, 0, 13, 14 ],
  [ 4, 5, 6, 0, 1, 1 ]
]
[
  [ 3, 0, 9, 10, 11, 12 ],
  [ 2, 0, 8, 0, 12, 0 ],
  [ 3, 0, 7, 0, 13, 14 ],
  [ 4, 5, 6, 0, 14, 1 ]
]
[
  [ 3, 0, 9, 10, 11, 12 ],
  [ 2, 0, 8, 0, 12, 0 ],
  [ 3, 0, 7, 0, 13, 14 ],
  [ 4, 5, 6, 0, 14, 15 ]
]
15