[알고리즘] 위상정렬(Topology Sort)

참고 자료

• GeeksForGeeks : https://www.geeksforgeeks.org/topological-sorting/?ref=header_outind
• youngeui_hong.log : https://velog.io/@youngeui_hong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC-%EB%AC%B8%EC%A0%9C-%EC%B4%9D-%EC%A0%95%EB%A6%AC
• Claude AI ( 문법 확인용 )

---

🖐️[알고리즘] 위상정렬(Topology Sort)

위상정렬은 순환성이 없는 방향 그래프(DAG)에서 사용 가능한 알고리즘이며, 결과 값으로 그래프의 노드들을 선형적으로 나타낸다. 이때 결과 값은 항상 일정하지 않다.

 

위 이미지에서 위상정렬을 통해서 결과 값을 나타내면 다음과 같은 값이 나올 수 있다.

5 -> 4 -> 2 -> 3 -> 1 -> 0
4 -> 5 -> 2 -> 3 -> 1 -> 0

 

많은 사람들이 예시로 대학교 과목을 수강하기 전, 선행이 필요한 과목, 외출할 때 준비 순서, 등을 이야기 하는데 나는 크게 와닿지가 않아서 문제 풀이를 기반으로 위상정렬 알고리즘을 이해하고 넘어갔다. 위상정렬 학습에 필요한 정보를 보자.

 

---

☑️ 진입차수(Indegree), 진출차수(OutDegree)

•  진입차수(Indegree)
  • 어떤 노드 A로 들어오는 간선의 개수
• 진출차수(Outdegree)
  • 어떤 노드 A에서 나가는 간선의 개수

 

이해하기 어려운 개념은 아니고 어떤 노드 A가 있을 때, 진입하는 간선과 진출하는 간선의 수를 말하는 것이 된다. 노드마다 진입차수, 진출차수는 다르다.

https://velog.io/@youngeui_hong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC-%EB%AC%B8%EC%A0%9C-%EC%B4%9D-%EC%A0%95%EB%A6%AC

 

---

☑️ 위상정렬 구현 방법

위상정렬을 풀어내는 방법은 Queue와 Stack이 있다. 이 중에서 Queue를 사용하는 방법을 보자.

1. 진입차수가 0인 노드를 Queue에 삽입한다.
2. Queue에서 노드를 꺼내고 해당 노드와 이어진 노드의 간선을 제거한다.
3. 진입차수가 0인 노드가 있는지 검색하고 있을 경우, Queue에 삽입한다.
4. Queue가 빌 때 까지 2번부터 3번을 반복한다.

 

---

☑️ 문제

이제 사용 방법에 대해서 알기 위해서 위상정렬 문제를 풀면서 생각해보자.

[Python, 2252번] 줄 세우기