[백준][다익스트라] 4485 녹색 옷 입은 애가 젤다지? NodeJs 구현

목차

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

문제

 

문제 구현 방향

기존 인접리스트와 마찬가지로 가중치와 인접 노드를 통해 똑같이 구현해주면 된다.

bfs와 유사한 꼴이니까 다익스트라는 외우면 쉬운 것 같다.

 

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

class MinHeap {
  arr = [];
  parent = (idx) => Math.floor((idx - 1) / 2);
  left = (idx) => idx * 2 + 1;
  right = (idx) => idx * 2 + 2;
  last = () => this.arr.length - 1;
  swap = (a, b) => ([this.arr[a], this.arr[b]] = [this.arr[b], this.arr[a]]);

  isEmpty = () => this.arr.length === 0;

  push(data) {
    this.arr.push(data);
    let now = 0;
    while (now > 0 && this.arr[now][1] < this.arr[this.parent(now)][1]) {
      const parent = this.parent(now);
      this.swap(now, parent);
      now = parent;
    }
  }

  pop() {
    this.swap(0, this.last());
    const result = this.arr.pop();
    let [now, left, right] = [0, 1, 2];
    while (left <= this.last()) {
      let change = left;
      if (right <= this.last() && this.arr[right][1] < this.arr[left][1]) {
        change = right;
      }
      if (this.arr[change][1] < this.arr[now][1]) {
        this.swap(change, now);
        now = change;
        left = this.left(now);
        right = this.right(now);
      } else break;
    }
    return result;
  }
}

let idx = 0;

let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];
function bfs(board, visit, x, y) {
  let n = board[0].length;
  let pq = new MinHeap();
  pq.push([[x, y], board[y][x]]);
  visit[y][x] = board[y][x];
  while (!pq.isEmpty()) {
    let t = pq.pop();

    for (let i = 0; i < 4; i++) {
      let nx = t[0][0] + dx[i];
      let ny = t[0][1] + dy[i];

      if (nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1) continue;
      let dist = t[1] + board[ny][nx];
      if (dist < visit[ny][nx]) {
        pq.push([[nx, ny], dist]);
        visit[ny][nx] = dist;
      }
    }
  }
}
let cnt = 1;
while (idx < input.length) {
  let n = +input[idx];
  if (n === 0) break;
  let visit = [];
  let board = [];
  for (let j = 0; j < n; j++) {
    idx++;
    let ar = input[idx].trim().split(" ").map(Number);
    board.push(ar);
    visit.push(Array(ar.length).fill(9999999999));
  }
  bfs(board, visit, 0, 0);
  idx++;
  console.log(`Problem ${cnt++}:`, visit[n - 1][n - 1]);
}