14940 쉬운 최단거리 node.js

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

단순한 dfs문제였습니다. 그런데, js에는 queue가 없어서 queue를 구현해서 사용해야 합니다.

Queue 구현과정

2개의 stack을 만들어두고, 들어오는대로 AStack 에 push
popleft 가 실행될 때는 BStack 에서 pop해서 하나씩 return하는 형태입니다. 이 때, BStack이 비어있다면, Astack이 빌 때까지 pop한 후 BStach에 push합니다.

A -> B -> C 순으로 push한 결과

popleft가 일어났을 때, inbox에서 모든 요소를 차례로 pop한 후 outbox에 push하면 역순으로 담기게된다.

class Queue {
  constructor() {
    this.inbox = []; // 새로운 요소를 추가하는 스택
    this.outbox = []; // 요소를 제거하는 스택
  }

  // 큐에 요소를 추가 (FIFO의 끝에 추가)
  push(value) {
    this.inbox.push(value); // 스택에 푸시 (O(1))
  }

  // 큐에서 요소를 제거 (FIFO의 맨 앞 요소 제거)
  popleft() {
    if (this.outbox.length === 0) {
      // outbox가 비어있으면 inbox의 모든 요소를 outbox로 이동
      while (this.inbox.length > 0) {
        this.outbox.push(this.inbox.pop());
      }
    }
    return this.outbox.pop();
  }
}

문제 풀이

문제는 간단하게 dfs로 풀었다.

class Queue {
  constructor() {
    this.inbox = []; // 새로운 요소를 추가하는 스택
    this.outbox = []; // 요소를 제거하는 스택
  }

  // 큐에 요소를 추가 (FIFO의 끝에 추가)
  push(value) {
    this.inbox.push(value); // 스택에 푸시 (O(1))
  }

  // 큐에서 요소를 제거 (FIFO의 맨 앞 요소 제거)
  popleft() {
    if (this.outbox.length === 0) {
      // outbox가 비어있으면 inbox의 모든 요소를 outbox로 이동
      while (this.inbox.length > 0) {
        this.outbox.push(this.inbox.pop());
      }
    }
    return this.outbox.pop();
  }

  isEmpty() {
    return this.inbox.length === 0 && this.outbox.length === 0;
  }
}

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

const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];
const [X, Y] = input[0].split(' ').map(Number);
const board = [];
let startPos = [-1, -1, 0];
for (let i = 0; i < X; i++) {
  const row = input[i + 1].split(' ').map((el, j) => {
    if (el == 2) {
      startPos = [i, j, 0];
      return 'G';
    } else if (el == 1) return 'O';
    else if (el == 0) return 'X';
  });
  board.push(row);
}

const q = new Queue();
q.push(startPos);

while (!q.isEmpty()) {
  const [currentX, currentY, cnt] = q.popleft();
  for (let i = 0; i < 4; i++) {
    const [nx, ny] = [currentX + dx[i], currentY + dy[i]];
    if (nx < 0 || ny < 0 || nx >= X || ny >= Y) continue;
    if (board[nx][ny] != 'O') continue;
    board[nx][ny] = cnt + 1;
    q.push([nx, ny, cnt + 1]);
  }
}

for (let i = 0; i < X; i++) {
  console.log(
    board[i]
      .map((el) => {
        if (el == 'G') return 0;
        else if (el == 'X') return 0;
        else if (el == 'O') return -1;
        else return el;
      })
      .join(' ')
  );
}