boj_1966.js

// let input = `4 2
// 4 2
// 3 1`
//   .trim()
//   .split("\n");

// input 파싱
// let input = require("fs").readFileSync("/dev/stdin").trim().split("\n");

// 위상정렬에 필요한 기본 그래프 생성
class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }
  addEdge(v1, v2) {
    if (v1 in this.adjacencyList) {
      this.adjacencyList[v1].push(v2);
    }
  }
}

// dfs 정렬을 위한 구현체
const dfsTopSortHelper = (graph, v, n, visited, topNums) => {
  visited[v] = true;
  const neighbors = graph.adjacencyList[v];
  for (const neighbor of neighbors) {
    if (!visited[neighbor]) {
      n = dfsTopSortHelper(graph, neighbor, n, visited, topNums);
    }
  }
  topNums[v] = n;
  return n - 1;
};
const dfsTopSort = (graph) => {
  const vertices = Object.keys(graph.adjacencyList);
  const visited = {};
  const topNums = {};
  let n = vertices.length - 1;
  for (const v of vertices) {
    if (!visited[v]) {
      n = dfsTopSortHelper(graph, v, n, visited, topNums);
    }
  }
  return topNums;
};

const graph = new Graph();
const [firstInput, ...restInput] = input;
const [problemCount, conditionCount] = firstInput.split(" ").map(Number);

// 전체 순서에 따른 기본 노드 생성
for (let i = 0; i < problemCount; i++) {
  graph.addVertex(i + 1);
}

// 우선순위에 대한 정보 입력
restInput.forEach((item) => {
  const [beforeNumber, afterNumber] = item.split(" ");
  graph.addEdge(afterNumber, beforeNumber);
});

const anwser = new Array(problemCount).fill(0);

// 위상정렬 알고리즘 실행 (dfs)
const topologyArray = dfsTopSort(graph);

// 정렬된 값을 읽어가며 정답배열 생성
// { '1': 2, '2': 0, '3': 3, '4': 1 }
for (let key in topologyArray) {
  anwser[problemCount - topologyArray[key] - 1] = key;
}

console.log(anwser.map(Number).join(" "));