💡문제 분석 요약

• 미로 탐색 문제
• 1과 0으로 이루어진 미로에서 (1, 1)에서 출발하여 (N, M)에 도착할 때, 최단 경로의 길이를 구해야 한다.
  • 1은 이동할 수 있는 길, 0은 벽
  • 상하좌우로만 이동할 수 있다.

💡알고리즘 설계

• 큐 초기화: BFS에서는 큐를 사용하여 탐색할 좌표를 관리한다. 시작 좌표 (0, 0)을 큐에 넣고 탐색을 시작한다.
• 방문 처리: 방문한 좌표는 다시 방문하지 않도록 visited 배열에 기록한다.
• 상하좌우 탐색: 현재 좌표에서 상, 하, 좌, 우로 이동 가능한지 확인하고, 갈 수 있으면 큐에 넣고, 이동한 좌표에 이전 좌표 값에서 +1한 값을 저장한다.
• 도착 확인: BFS에서 (N-1, M-1)에 도착하면 그때의 값이 최단 경로가 된다.

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split('\\n');

// 입력값 처리
const [N, M] = input[0].split(' ').map(Number); // 첫 줄에서 N과 M 값 가져옴
const maze = input.slice(1).map(line => line.split('').map(Number)); // 나머지 줄에서 미로 정보 가져옴

function bfs(maze, N, M) {
  const directions = [
    [0, 1],  // 오른쪽
    [1, 0],  // 아래쪽
    [0, -1], // 왼쪽
    [-1, 0]  // 위쪽
  ];

  const queue = [[0, 0]]; // 시작점 (0, 0)
  const visited = Array.from({ length: N }, () => Array(M).fill(false));
  visited[0][0] = true;

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

    // 도착지에 도달하면 그 칸의 값을 리턴 (최단 경로)
    if (x === N - 1 && y === M - 1) {
      return maze[x][y];
    }

    // 상하좌우 탐색
    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;

      // 범위를 벗어나지 않고, 벽이 아니고, 아직 방문하지 않았다면
      if (nx >= 0 && ny >= 0 && nx < N && ny < M && maze[nx][ny] === 1 && !visited[nx][ny]) {
        queue.push([nx, ny]);
        visited[nx][ny] = true;
        maze[nx][ny] = maze[x][y] + 1; // 이전 경로에서 +1
      }
    }
  }

  return -1; // 도달할 수 없는 경우
}

// 최단 경로 출력
console.log(bfs(maze, N, M));

💡시간복잡도

• 시간 복잡도 O(N * M)
• 미로의 모든 칸을 한 번씩 탐색하기 때문에 칸 수만큼 시간이 걸린다