Node.js) 백준 16964번: DFS 스페셜 저지

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

16964번: DFS 스페셜 저지

class Node {
  constructor(item) {
    this.item = item;
    this.prev = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(item) {
    const node = new Node(item);
    if (this.top != null) {
      node.prev = this.top;
    }
    this.top = node;
    this.length++;
  }

  pop() {
    if (this.length > 0) {
      const popItem = this.top;
      this.top = this.top.prev;
      this.length--;
      return popItem.item;
    } else {
      return false;
    }
  }
}

const fs = require("fs");
const input = fs
  .readFileSync("./dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

const [N] = input.shift();
const target = input.pop();

// 우선순위
const priority = [];
for (let i = 0; i < target.length; i++) {
  priority[target[i]] = i;
}

// 인접리스트
let edge = Array.from(Array(N + 1), () => Array());
input.forEach((v) => {
  const [x, y] = v;
  edge[x].push(y);
  edge[y].push(x);
});

//우선순위에 따른 인접 리스트 설정.
edge = edge.map((v) => v.sort((a, b) => priority[b] - priority[a]));

//dfs
const stack = new Stack();
stack.push(1);
let visited = new Array(N + 1).fill(false);
const answer = [];

while (stack.length > 0) {
  const now = stack.pop();
  answer.push(now);
  visited[now] = true;

  edge[now].forEach((v) => {
    if (!visited[v]) {
      stack.push(v);
    }
  });
}

if (answer.join(" ") == target.join(" ")) {
  console.log(1);
} else {
  console.log(0);
}