[BFS] 백준 미로탐색 자바스크립트(Node.JS) 버전

자바스크립트(node.js)로 이루어진 알고리즘 풀이가 구글검색 결과에 거의 없는것 같습니다. 이 포스트가 자바스크립트로 알고리즘을 공부하시는 분들께 도움이 되면 좋겠습니다.

BFS의 원리

BFS탐색기법에서는 큐(Queue)가 핵심입니다. 큐를 활용하여서 BFS를 구현할 수 있기 때문입니다. 큐가 BFS를 구현할 수 있는 원리는 선입선출(FIFO _ first in first out) 구조이기 때문입니다. 구체적으로 설명하자면, 한 노드와 연결되어 있는 자식 노드(하위레빌)가 일단 큐에 들어가게 되고 그 자식노드와 연결되어 있는 자식노드(하위레벨)는 큐의 맨 뒤로 들어가게 되는 것입니다. 그리하여 상위레벨의 탐색이 먼저 이루어지고 난 뒤 자식노드로의 접근이 이루어 지게 되는 것입니다.

BFS는 어떻게 최단거리를 찾을 수 있는가?

4곱하기 4 미로가 있다고 가정해보겠습니다.

시작점에서 인접한 노드는 동쪽과 남쪽에 있는 두개입니다. 북, 동, 남, 서 순서로 큐에 넣는다고 가정하겠습니다.

시작 (1, 1)	통로 (2, 1) 첫번째	통로	통로	통로
통로	벽	벽	벽	통로
통로	벽	통로	통로	통로
통로	벽	통로	벽	통로
통로	통로	통로	벽	도착 (5, 5)

임의로 정한 북, 동, 남, 서 순서에 의해 (2, 1)좌표의 노드가 먼저 큐에 들어가게 됩니다. 그 후 (1, 2)의 노드가 큐에 들어갑니다.

시작 (1, 1)	통로 (2, 1) 첫번째	통로	통로	통로
통로 (1, 2) 두번째	벽	벽	벽	통로
통로	벽	통로	통로	통로
통로	벽	통로	벽	통로
통로	통로	통로	벽	도착 (5, 5)

(2,1)좌표의 노드가 먼저 들어갔으니 큐에서 먼저 나오고 연결되어 있는 노드중 통로이면 큐에 넣게 됩니다. 이때 큐에는 (1, 2)의노드가 이미 있기에 이 뒤로 들어가게 되는 것입니다.

시작 (1, 1)	통로 (2, 1) 첫번째	통로 (3, 1) 세번째	통로	통로
통로 (1, 2) 두번째	벽	벽	벽	통로
통로	벽	통로	통로	통로
통로	벽	통로	벽	통로
통로	통로	통로	벽	도착 (5, 5)

시작 (1, 1)	통로 (2, 1) 첫번째	통로 (3, 1) 세번째	통로	통로
통로 (1, 2) 두번째	벽	벽	벽	통로
통로 (1, 3) 네번째	벽	통로	통로	통로
통로	벽	통로	벽	통로
통로	통로	통로	벽	도착 (5, 5)

시작 (1, 1)	통로 (2, 1) 첫번째	통로 (3, 1) 세번째	통로 (4, 1) 다섯번째	통로
통로 (1, 2) 두번째	벽	벽	벽	통로
통로 (1, 3) 네번째	벽	통로	통로	통로
통로	벽	통로	벽	통로
통로	통로	통로	벽	도착 (5, 5)

시작 (1, 1)	통로 (2, 1) 첫번째	통로 (3, 1) 세번째	통로 (4, 1) 다섯번째	통로
통로 (1, 2) 두번째	벽	벽	벽	통로
통로 (1, 3) 네번째	벽	통로	통로	통로
통로 (1, 4) 여섯번째	벽	통로	벽	통로
통로	통로	통로	벽	도착 (5, 5)

 

[최종적으로 큐로 들어간 노드의 순서]

최종적으로는 다음과 같은 순서로 큐로 들어가게 되는 것입니다. 밑의 숫자는 큐에 들어가는 순서이며 거리를 의미하는 것은 아닙니다.

시작	1	3	5	7
2	벽	벽	벽	9
4	벽	15	13	11
6	벽	14	벽	13
8	10	12	벽	15 도착

 

코드로 구현하기

우선 큐를 클래스 문법을 통해서 만들었습니다.  (백준 채점 시스템은 현재 Node.JS 버전10이며, ES6를 지원하기에 클래스 문법이 가능합니다.)

백준 알고리즘을 node.js로 풀때 또 중요한것이 node.js의 입력과 출력을 잘 알고 있어야 한다는 것입니다. 저는 백준에서 명시하고 있는 표준 입출력 방식은 아니지만 readline이라는 내장 모듈을 사용했습니다.

const readline = require("readline");

class Queue {
  constructor() {
    this.data = [];
  }
  enqueue(params) {
    this.data.push(params);
  }
  dequeue() {
    return this.data.shift();
  }
  isEmpty() {
    if (this.data.length === 0) {
      return true;
    } else {
      return false;
    }
  }
}

function Location(x, y) {
  (this.curX = x), (this.curY = y);
}

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let map = [];
let cnt = 0;
let N = 0;
let M = 0;

rl.on("line", function(line) {
  if (cnt === 0) {
    N = parseInt(line.split(" ")[0]);
    M = parseInt(line.split(" ")[1]);
  }
  if (cnt >= 1) {
    map.push(line.split("").map(Number));
  }
  if (cnt === M) {
    rl.close();
  }
  cnt++;
}).on("close", function() {
  const dx = [0, 1, 0, -1]; // 북, 동, 남, 서
  const dy = [1, 0, -1, 0]; // 북, 동, 남, 서

  const queue = new Queue();
  map[0][0] = -1;
  const location = new Location(0, 0);
  queue.enqueue(location);
  outer: while (!queue.isEmpty()) {
    let loc = queue.dequeue(); // 큐에서 나온 위치 객체
    for (let i = 0; i < 4; i++) {
      let _x = loc.curX + dx[i];
      let _y = loc.curY + dy[i];

	 // 범위를 넘어가면
      if (_x < 0 || _y < 0 || _x >= N || _y >= M) {
        continue;
      }
	 // 이미 방문한 노드면
      if (map[_x][_y] === -1) {
        continue;
      }

      // 북, 동, 남, 서 차례로 검사해서 길이 있으면
      if (map[_x][_y] === 1) {
        // 좌표를 가지고 있는 위치 인스턴스를 생성한다.
        const location = new Location(_x, _y);
        // 큐에 위치 인스턴스를 넣는다.
        queue.enqueue(location);
        // 지도에 몇번째 시도로 도착했는지 흔적을 남긴다 (지도의 자연수와 섞이지 않게 음수로 흔적을 남김)
        map[_x][_y] = map[loc.curX][loc.curY] - 1;
        if (_x === N - 1 && _y === M - 1) {
          break outer; // 바깥 while문을 탈출한다.
        }
      }
    }
  }
  console.log(map[N - 1][M - 1] * -1); // 거리를 출력
});

 

주석 처리를 통해서 코드 설명을 했습니다. 기타 궁금한 점들이 있으면 댓글 달아주세요.