알고리즘 준비하기

🎯 위상 정렬이란?

위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 가장 이해하기 쉬운 예로는 게임 캐릭터 키우기(?)가 있다.

예를 들어 주먹으로 때리기는 맨 처음에 배우는 기본 스킬이다. 하지만 몸통 박치기는 주먹으로 때리기라는 스킬을 배워야만 배울 수 있는 스킬이다. 또 고함 지르기 역시 주먹으로 때리기를 배워야만 익힐 수 있는 스킬이다. 필살기는 몸통 박치기와 고함 지르기를 모두 익혀야만 배울 수 있는 스킬이다.

이러한 흐름은 조건을 걸어줘서 해석할 수 있다. 한마디로 모든 일에 순서 제약이 걸려있는 셈이다. 위상 정렬은 사이클이 존재하지 않는 방향 그래프여야 한다는 전제조건이 있다. 사이클이 발생하면, 시작점이 없기 때문에 위상 정렬을 수행할 수 없기 때문이다.

🎯 위상 정렬 구현하는 법 (JS)

위상 정렬을 수행하는 알고리즘은 Queue를 이용하여 구현하 수 있다.

모든 관계는 그래프화가 되어 있다고 가정한다.
해당 노드에 연결되는 들어오는 지점이 몇개 연결되어 있는지 배열에 초기화한다.
만약 배열 값이 0이라면 Queue에 넣어둔다.
While문을 통해 shift를 한 값을 정답 배열에 넣어둔다. 그리고 해당 값이 들어가는 값이 되는 값을 모두 그래프에서 찾아서 해당 값이 포함된 배열에 값을 1씩 줄여준다.
만약 이 상황에서 0이 된다면 Queue에 넣어준다.
4~6번을 반복한다.

🎯 문제로 확인하기 (JS)

👉 문제 확인하기 : BOJ - 줄 세우기

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M] = input.shift().split(' ').map(Number);
let graph = Array.from({ length: N + 1 }, () => Array());
let inDegree = Array(N + 1).fill(0);

for (let i = 0; i < M; i += 1) {
  const [tall, small] = input[i].split(' ').map(Number);
  graph[tall].push(small);
  inDegree[small] += 1;
}

let queue = [];
let answer = [];
for (let i = 1; i <= N; i += 1) {
  if (inDegree[i] === 0) queue.push(i);
}

while (queue.length) {
  let prev = queue.shift();
  answer.push(prev);

  for (let next of graph[prev]) {
    inDegree[next] -= 1;
    if (inDegree[next] === 0) queue.push(next);
  }
}

console.log(answer);

📑 Reference

안경잡이개발자 - 위상 정렬

🎯 위상 정렬이란?
🎯 위상 정렬 구현하는 법 (JS)
🎯 문제로 확인하기 (JS)
📑 Reference