백준 2252 < 줄 세우기 > JavaScript

📍문제 링크

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

2252번: 줄 세우기

 

📍알고리즘 분류

- 그래프 이론

- 위상 정렬

 

📍문제 풀이

N명의 학생을 줄세우려 한다. M개의 선, 후 정보가 주어질 때 모든 학생을 줄세우는 아무 방법을 출력한다

- 답이 여러개일 수 있음

 

1 <= N <= 32,000

1 <= M <= 100,000

 

이므로, naive하게 줄 세우는 방법을 시도하면 O(N * M) 만 해도 엄청난 시간이 걸린다

 

그래프에 기반한 위상 정렬로 문제를 해결할 수 있다

 

1. 먼저, 유향그래프의 인접 리스트를 생성한다

/*
{
간선형태
출발 -> 도착
  1: [],
  2: [],
  3: [],
  ...
  N: []
}
*/

 

2. 정점별 진입 차수 (간선에서 도착지가 되는 횟수) 를 기록하는 배열을 생성한다

- 인덱스를 정점 번호로 하여 횟수를 원소로 담는다

- 원소가 1 이상이라는 것은 위치가 뒤로 간다는 의미이다

- 진입 차수가 0인 정점은 반드시 존재한다 (순서가 맨 앞인 정점은 무조건 진입 차수가 0이므로)

 

3. DFS를 통해 진입 차수가 0인 정점을 순회한다

- 방문하고 나면 해당 정점의 진입 차수를 -1 해준다

- 진입 차수가 0이면 stack에 push한다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

const dfs = (N, Graph, InDegree) => {
  const stack = [];
  const result = [];
  for (let i = 1; i <= N; i++) {
    if (!InDegree[i]) stack.push(i);
  }
  while (stack.length) {
    const currentNode = stack.pop();
    result.push(currentNode);
    Graph[currentNode].forEach((nextNode) => {
      InDegree[nextNode] -= 1;
      if (!InDegree[nextNode]) stack.push(nextNode);
    });
  }
  return result;
};

rl.on("line", (line) => {
  input.push(line.split(" ").map(Number));
}).on("close", () => {
  const [N, M] = input[0];
  const graph = {};
  // 진입 차수(간선에서 도착 횟수)를 기록할 배열
  const inDegree = Array.from({ length: N + 1 }, (_) => 0);
  // 정점 생성
  for (let i = 1; i <= N; i++) {
    graph[i] = [];
  }
  // 간선 생성 및 진입 차수 기록
  for (let i = 1; i <= M; i++) {
    const [prev, next] = input[i];
    graph[prev].push(next);
    inDegree[next] += 1;
  }
  console.log(dfs(N, graph, inDegree).join(" "));
});