[Javascript/자바스크립트] 백준 2178번 미로 탐색

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

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  push(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }

  popleft() {
    if (this.head) {
      const value = this.head.value;
      this.head = this.head.next;
      this.size--;
      return value;
    } else {
      return null;
    }
  }
}

function solution(n, m, arr) {
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];
  const visited = Array.from(new Array(n), () => new Array(m).fill(false));
  visited[0][0] = true;
  const que = new Queue();
  que.push([0, 0, 1]);
  while (que.size > 0) {
    const [x, y, cnt] = que.popleft();
    if (x === n - 1 && y === m - 1) return cnt;
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (
        nx >= 0 &&
        nx < n &&
        ny >= 0 &&
        ny < m &&
        !visited[nx][ny] &&
        arr[nx][ny] === "1"
      ) {
        visited[nx][ny] = true;
        que.push([nx, ny, cnt + 1]);
      }
    }
  }
}

const [n, m] = input[0].split(" ").map((value) => +value);
console.log(solution(n, m, input.slice(1)));

풀이

BFS를 구현할 때 양쪽에서 데이터 추가/삭제가 가능한 양방향 큐(Deque)가 필요하다.

파이썬으로 할 때는 deque를 사용하면 됐었는데, javascript에는 이런 양방향 큐 자료구조가 없다. 그래서 위와 같이 연결리스트 방식으로 deque를 구현했다.

 

배열이 아닌 연결리스트 방식으로 구현한 이유는 앞쪽에서 요소를 삭제 시에 더 효율적이기 때문이다.

배열은 shift() 연산을 이용하여 앞쪽의 요소를 하나 삭제할 수 있지만, 이렇게 하면 뒤의 요소를 모두 한 칸씩 땡겨와야하므로 삭제 연산의 시간복잡도가 O(n)이다.

그에 반해 연결 리스트는 이렇게 뒤의 요소들을 앞으로 땡겨오고 하는 작업이 필요가 없다. 그저 head가 가리키고 있는 요소, 즉 가장 앞에 있는 요소를 하나 삭제하기만 하고, head가 가리키는 노드를 삭제된 요소의 바로 뒷 요소로 바꿔주기만 하면 된다. 그렇기 때문에 연결리스트는 삭제 연산의 시간복잡도가 O(1)이다.

 

특히 BFS를 수행할 때에는 배열 앞쪽에서 삭제, 배열 뒤쪽에 삽입만 하면 되므로 연결리스트로 구현하는 것이 효율적이다.

(Javascript) 연결리스트로 Deque 구현

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  push(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }

  popleft() {
    if (this.head) {
      const value = this.head.value;
      this.head = this.head.next;
      this.size--;
      return value;
    } else {
      return null;
    }
  }
}

 

필요한 연산인 `push`(뒤쪽에 삽입)와 `popleft`(앞에서 뽑기)만 구현하여 사용했다.

참고 자료

- https://www.daleseo.com/js-array-pop-shift/

- https://velog.io/@brgndy/%EB%B0%B0%EC%97%B4-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%A0%95%EB%A6%AC%ED%95%B4%EB%B3%B4%EA%B8%B0