[자바스크립트] 2178 미로 탐색

2178번: 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

 

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

 

예제 입력 1

4 6
110110
110110
111111
111101

 

 

예제 출력 1

9

 

 

자료구조

① 정수: n, m, dx, dy

② 정수형 배열: arr, visited, queue

 

 

알고리즘

BFS (너비 우선 탐색)

① 초기화: BFS 탐색을 위한 큐 queue를 초기화하고, 시작 위치 (0, 0)를 큐에 추가.

② 탐색 루프: 큐 length 가 0이 아니면 계속 반복

• 큐에서 현재 위치 (x, y)를 꺼낸다.
• 상, 하, 좌, 우 네 방향으로 이동할 수 있는 위치를 계산한다.
• 이동할 수 있는 위치가 미로(1) 내에 있고, 아직 방문하지 않은 경로(false)인 경우:
  • 큐에 새로운 위치를 추가.
  • 해당 위치를 방문 처리하고, 현재 depth(거리)를 업데이트 한다.

③ 반환: 목표 위치에 도달했을 때의 방문 횟수를 반환한다.

 

 

소스 코드 

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [n, m] = input[0].split(" ").map(Number);
const arr = input.slice(1, n + 1).map((line) => line.split("").map(Number));
const visited = Array.from({ length: n }, () => Array(m).fill(false));

// 상, 하, 좌, 우 탐색을 위한 배열
const dx = [0, 0, -1, 1];
const dy = [1, -1, 0, 0];

function bfs(startX, startY) {
  const queue = [[startX, startY]];
  visited[startX][startY] = true;

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

    for (let k = 0; k < 4; k++) {
      const newX = x + dx[k];
      const newY = y + dy[k];

      if (0 <= newX && 0 <= newY && newX < n && newY < m) {
        if (arr[newX][newY] === 1 && !visited[newX][newY]) {
          queue.push([newX, newY]);
          arr[newX][newY] = arr[x][y] + 1;
          visited[newX][newY] = true;
        }
      }
    }
  }
}

bfs(0, 0);
console.log(arr[n - 1][m - 1]);

192ms

 

 

 

✔ 출처

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