위상 정렬 알아보기

위상 정렬(Topological Sorting)이란?

• 방향 그래프의 정점들을 방향을 거스르지 않도록 나열하는 것.
  • 각 정점에 순서를 매기고, 그 순서를 거스르지 않도록 정점들을 정렬하는 것을 의미한다. 
  • ex) 선수 과목 구조(과목마다 먼저 들어야 하는 과목의 순서가 정해져 있음)
• 여기서 순서란, 그래프의 정점 순서를 가리킴.
  • ex) 정점 v1과 v2이 v1 → v2 방향으로 연결되어 있으면, v1이 선행된다고 본다.
• 위상 정렬에 사용될 그래프는 순환이 없어야 함(비순환 방향 그래프여야 함).

 

알고리즘

Kahn 알고리즘

1. 자신을 향하는 간선(즉, 자신으로 들어오는 간선)이 없는 정점을 찾는다.
   이러한 정점이 여러 개라면, 그 중 아무거나 한 개를 고른다.
2. 해당 정점을 그래프에서 제거한다.
3. 남은 그래프에서 정점이 더 이상 존재하지 않을 때까지 위 과정을 반복한다.

 

 

문제 풀이 - 백준 2623번 음악프로그램

  위상정렬을 사용하여 가수들의 출연 순서를 결정하는 문제. 입력으로 들어오는, 보조 PD가 정한 순서를 사용하여 방향 비순환 그래프를 그리고, 이 그래프에 위상정렬을 사용하기만 하면 되는 문제다. 위상정렬의 구현 방법을 알기만 하면 바로 풀 수 있는 문제라, 위상정렬 알고리즘에 대해 공부한 후 바로 문제를 풀이할 수 있었다. 아래 코드에서는 위의 Kahn 알고리즘을 사용하였다.

 

  전체 코드는 아래와 같다.

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

let input = [];

rl.on("line", (line) => {
  input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
  const [n, m] = input.shift();
  const edgesInfo = new Array(n + 1).fill(0);
  let answer = [];

  const adjacencyList = {};
  for (let i = 1; i <= n; i++) {
    adjacencyList[i] = [];
  }

  const addEdges = (arr, length) => {
    for (let idx = 0; idx < length - 1; idx++) {
      adjacencyList[arr[idx]].push(arr[idx + 1]);
      edgesInfo[arr[idx + 1]]++;
    }
  };

  for (let i = 0; i < m; i++) {
    addEdges(input[i].slice(1), input[i][0]);
  }

  const queue = [];
  for (let i = 1; i < n + 1; i++) {
    if (edgesInfo[i] === 0) queue.push(i);
  }

  while (queue.length) {
    const v = queue.shift();
    adjacencyList[v].forEach(neighbor => {
      edgesInfo[neighbor]--;

      if (edgesInfo[neighbor] === 0) queue.push(neighbor);
    });

    answer.push(v);
  }

  if (answer.length !== n) {
    console.log(0);
    process.exit();
  }

  console.log(answer.join('\n').trimEnd());
  process.exit();
});

• 입력으로 들어오는, 보조 PD가 정한 순서를 사용하여 인접 리스트를 만든다.
• 인접 리스트를 만들며, 각 정점으로 들어오는 간선의 개수를 세어서 기록한다(edgesInfo 부분)
• 인접 리스트와 간선 개수를 다 구했다면, 자신으로 들어오는 간선의 개수가 없는 정점들을 골라 큐에 넣는다.
• 큐가 빌 때까지 큐의 요소를 꺼내어 아래의 과정을 반복한다.
  • 큐에서 꺼낸 정점에 연결된 이웃 정점들에 연결된 간선을 한 개씩 뺀다.
    • 이는 큐에서 꺼낸 정점을 그래프에서 제거함을 의미한다.
  • 간선을 빼고 난 후 자신으로 들어오는 간선의 수가 0이 된 정점이 생겨날 경우, 이 정점을 큐에 넣는다.
  • 큐에서 빼낸 정점은 answer 배열에 넣어 순서를 기록한다.
• 반복이 끝나고 정답 배열을 확인했을 때, 그 길이가 정점의 총 개수와 같다면 정답, 그렇지 않다면 주어진 순서 조건을 만족하는 경우의 수가 없다는 의미임으로 0을 출력한다.

---

• Kahn 알고리즘이 구현하기 쉬웠던 관계로 이번엔 이걸 사용해 풀이해봤는데, DFS로도 위상정렬을 구현할 수 있다는 것 같다.
• 나중엔 위상정렬과 관련된 다른 알고리즘을 좀 더 찾아보기로.