🚦 위상 정렬

🚦 위상 정렬(Topology Sort)

• 위상 정렬은 방향이 있고, 순환하지 않는 그래프에서 각 노드를 순서대로 나열하는 방법이다.
• 쉽게 말해 순서가 정해져 있는 일련의 작업들을 차례대로 수행해야 할 때 사용하는 알고리즘이다.
• 전형적인 예시로는 “선수과목 구조”가 있다.
  • 만약 특정 교과목에 선수과목이 존재한다면 선수과목부터 수강을 해야 특정 교과목을 수강할 수 있다.
  • 이때 위상정렬을 사용하면 올바른 수강 순서를 찾아낼 수 있다.

🚦 동작 원리

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

위 과정을 수행했을 때 각 노드가 큐에들어온 순서가 위상정렬을 수행한 결과가 된다.

진입차수란 ?
특정한 노드로 들어오는 간선의 개수

위 과정을 그림으로 살펴보자!

진입차수 가 0인 노드인 1번 노드를 큐에 넣는다.

큐에서 1번 노드를 꺼낸 뒤, 1번 노드에서 출발해 2번 노드, 5번 노드로 가는 간선 두개를 제거한다.

다시 진입차수가 0이 된 2번 노드와 5번 노드를 큐에 넣는다. 이 때 큐에 넣는 순서는 상관 없다. 어떤 노드를 먼저 수행해도 노드를 순서대로 방문하는 것에 위반되지 않기 때문이다.

큐에서 2번 노드를 꺼낸 뒤, 2번 노드에서 출발해 3번 노드, 6번 노드로 가는 간선 두개를 제거한다.

다시 진입차수가 0이 된 3번 노드를 큐에 넣는다.

큐에서 5번 노드를 꺼낸 뒤, 5번 노드에서 출발해 6번 노드로 가는 간선을 제거한다.

다시 진입차수가 0이 된 6번 노드를 큐에 넣는다.

큐에서 3번 노드를 꺼낸 뒤, 3번 노드에서 출발해 4번 노드로 가는 간선을 제거한다.

진입차수가 0이 된 노드가 없으므로 다음 단계로 넘어간다.

큐에서 6번 노드를 꺼낸 뒤, 6번 노드에서 출발해 4번 노드로 가는 간선을 제거한다.

다시 진입차수가 0이 된 4번 노드를 큐에 넣는다.

큐에서 4번 노드를 꺼낸 뒤, 4번 노드에서 출발해 7번 노드로 가는 간선을 제거한다.

다시 진입차수가 0이 된 7번 노드를 큐에 넣는다.

큐에서 7번 노드를 꺼낸다. 7번 노드에서 나가는 간선이 없고, 진입차수가 0이된 노드가 없으므로 순회를 종료한다.

각 노드가 큐에 들어온 순서, 즉 위상정렬을 수행한 결과는 다음과 같다.

1 → 2 → 5 → 3 → 6 → 4 → 7

만약 스텝 2에서 5번 노드를 먼저 넣어줬다면 위상정렬을 수행한 결과는 다음과 같을 것이다.

1 → 5 → 2 → 3 → 6 → 4 → 7

이처럼 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우 위상정렬을 수행한 결과는 여러개가 된다.

또한 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 사이클이 있는 경우 사이클 내의 노드들은 순서를 정할 수 없기에 어떤 노드도 큐도 들어갈 수가 없기 때문이다.

🚦 소스코드(JS)

// 입력 값 첫 요소는 노드의 개수와 간선의 개수
// 이후 n개의 요소는 간선의 정보(시작 노드 끝 노드)
const inputs = ['7 8', '1 2', '1 5', '2 3', '2 6', '3 4', '4 7', '5 6', '6 4'];
const [n, e] = inputs.shift().split(' ').map(Number);

// 그래프 간선 정보를 저장할 배열
const graph = Array.from({ length: n + 1 }, () => []);

// 각 노드별 진입 차수를 계산할 배열
const indegree = Array(n + 1).fill(0);
const q = [];

// 간선 정보를 순회하며 시작 노드와 끝 노드를 그래프에 넣고, 진입차수를 계산한다.
for (const input of inputs) {
  const [s, e] = input.split(' ').map(Number);

  graph[s].push(e);
  indegree[e] += 1;
}

// 모든 간선정보와 진입차수를 입력받은 뒤 진입차수가 0인 노드를 찾아 큐에 넣어준다.
for (let i = 1; i <= n; i++) {
  if (indegree[i] === 0) q.push(i);
}

// 큐가 빌때까지 순회
while (q.length) {
  const current = q.shift();

  // 큐에 방문한 순서가 위상정렬을 수행한 순서
  // 즉 출력되는 노드 순서가 위상정렬을 수행한 결과
  console.log(current);

  // 현재 노드와 연결된 간선을 제거함
  for (const next of graph[current]) {
    indegree[next] -= 1;

    // 새롭게진입차수가 0인 노드를 큐에 삽입
    if (indegree[next] === 0) q.push(next);
  }
}

🚦 시간 복잡도

위상 정령의 시간복잡도는 O(V + E)이다. 모든 노드를 확인하고, 모든 간선의 확인하기 때문이다.

🚦 위상정렬 문제 추천

• 백준 선수과목 (Prerequisite)
• 백준 줄 세우기
• 백준 음악프로그램
• 백준 계보 복원가 호석
• 백준 문제집작업
• 백준 ACM Craft
• 백준 장난감 조립

🚦 Ref

• 이것이 취업을 위한 코딩테스트다
• [이것이 코딩 테스트다 with Python] 30강 다익스트라 최단 경로 알고리즘
• 위상정렬 위키피디아렬 위키피디아