위상 정렬(topological sorting)

위상 정렬(topological sorting)이란?

사이클이 없는 방향 그래프에서 작업의 순서가 정해져 있을 때 작업을 정확하게 정렬해주는 알고리즘이다.

즉, 시작점이 존재해야만 하고 순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정해야할 때 사용하는 알고리즘이다.

구현 방식

Queue를 사용하는 방식과 Stack을 사용하는 방식이 있는데, 여기서는 Queue를 이용하는 방식을 사용할 것이다.

1) 연결 상태를 저장한다.

4->6: arr[4].add(6)
5->6: arr[5].add(6)

2) 각 원소의 진입 차수를 계산한다.

진입 차수는 각 원소로 들어오는 원소의 개수를 말한다.
예를 들면, '2'의 진입차수는 '1'만 들어오므로 1개이고, '6'의 진입 차수는 '4'와 '5'가 들어오므로 2이다.

3) 탐색하며 진입 차수가 0인 것들을 Queue에 넣어주고, 간선을 제거한다.

4) 또다시 진입차수가 0인 것들을 Queue에 넣는다.

5) 정렬이 완전히 수행되려면 모든 원소들을 방문해야 한다. 그러므로 모든 원소를 방문하기 전에 queue가 비어있다면 false를 반환한다.

관련 문제

• leetcode 207. Course Schedule

  -> 풀이: 릿코드 207. Course Schedule

• 백준 줄 세우기