백준2252 - 줄 세우기 (위상정렬) node.js

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

이 문제를 맞닥뜨렸을 때, 어떻게 풀지 오래 고민하다가 구글의 도움을 받았다. 그리고 이로부터 알게 된 개념은 위상 정렬에 대한 개념. 내 알고리즘 풀이 실력에 비해 너무 어렵거나 쉽지 않아 재밌게 공부할 수 있었다.



위상 정렬의 정의

위상 정렬은 방향 그래프에서 각 정점들의 선후 관계에 따라 정점을 나열하는 알고리즘으로, 해당 알고리즘은 선행 관계가 있는 것들을 순서에 맞게 정렬하는 방법, 또는 의존성을 파악하거나 순서에 맞게 수행할 때 유용한 방법이라고 한다.

 

위상 정렬의 단계

1. 진입차수 계산 - 각 정점의 진입차수(입력으로 들어오는 간선의 수)를 계산한다. 이는 각 정점이 몇 개의 선행 작업을 가지고 있는지를 의미한다.
2. 진입차수가 0인 정점 선택 - 진입차수가 0인 정점은 선행 작업이 없는 작업들을 의미한다. (선행으로 처리해야 할 정점을 의미)
3. 선택한 정점 제거 - 해당 작업을 완료시킨다.
4. 진입 차수 업데이트 - 선택한 정점을 제거한 후, 그와 연결된 정점들의 진입차수를 감소시킨다. 이는 선택한 작업으로 인해 선행 작업의 수가 줄어든 것을 반영하는 의미기도 하다.
5. 진입차수가 0인 정점 선택 및 제거 - 위의 2~4단계를 반복하여 진입차수가 0인 정점을 선택하고 제거한다. 이 과정을 모든 정점이 제거될 때까지 반복한다.
6. 결과반환 - 정점들을 제거한 순서대로 나열하여 위상 정렬의 결과를 반환한다.

 

그리고 이 개념을 적용시켜 해당 문제를 풀이하면 다음과 같다.

전체 소스 코드

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

function solution(data) {
  const [[N, _], ...arr] = data.map((el) => el.split(" ").map(Number));
  
  // 그래프 배열
  const graph = Array.from({ length: N + 1 }, () => []);
  // 진입차수 배열
  const rank = Array.from({ length: N + 1 }, () => 0);

  arr.forEach(([a, b]) => {
    // 선행 노드 a의 그래프 안에 노드 b 추가
    graph[a].push(b);
    // 1. 진입 차수 계산
    // 선행 노드 a가 존재하는 노드 b의 진입차수 증가 
    rank[b]++;
  });
  
  // queue 구현
  const queue = [];
  let queueIdx = 0;

  for (let i = 1; i < N + 1; i++) {
    // 2. 진입차수가 0인 정점 선택
    if (!rank[i]) queue.push(i);
  }

  const result = [];
  while (queueIdx < queue.length) {
    const node = queue[queueIdx++];
    // 3,5. 선택한 정점 제거
    result.push(node);
    // 4. 진입차수 업데이트 ->선택한 정점과 연결된 정점들의 진입차수 감소
    graph[node].forEach((next) => {
      rank[next]--;
      // 5. 진입차수가 0인 정점 선택
      if (!rank[next]) queue.push(next);
    });
  }
  
  // 6. 결과반환
  console.log(...result);
}

solution(input);