위상정렬
- 사이클이 없는 방향 그래프(DAG)를 순서대로 나열하는 정렬 방법이다.
- 이벤트간의 우선순위나 종속성을 반영한 정렬을 할 때 사용한다.
- 사이클이 존재하는 경우, 이벤트간 우선순위에 따른 정렬을 할 수 없다.
위상정렬 활용
-
Course, Schedule Tree 등 이벤트, 트리거의 순서가 있을 때, 이를 정렬하는 문제들에 활용한다.
-
그래프에 사이클의 유무를 확인할 때 활용한다.
위상정렬 구현
-
그래프를 먼저 구현한다. (리스트, 딕셔너리)
-
들어오는 Edge가 없는 Vertex를 확인하고 큐에 append 한다.
(즉, indegree= 0 인 경우) -
큐에서 순서대로 해당 Vertex를 방문하면서, indegree를 1씩 빼준다. 이 때, indegree=0인 경우 큐에 추가해준다.
-
위 과정을 큐의 요소가 없어질 때까지 반복한다.
-
방문한 vertex와 그래프의 vertex가 같다면 (즉, 개수가 같다면) 사이클이 없는 위상 정렬된 그래프이다.
위상정렬 예제 - 207. Course Schedule
문제링크 : https://leetcode.com/problems/course-schedule/description/
작성 코드
from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
course_visited = []
graph = [[] for _ in range(numCourses)]
indegrees = [0]*numCourses
# 그래프 생성
for v, n in prerequisites:
graph[n].append(v)
indegrees[v] += 1
# indegress = 0인 vertex 값 대입
q=deque()
for i in range(len(indegrees)):
if indegrees[i] == 0:
q.append(i)
# 그래프 수행
while q:
cur_n = q.popleft()
course_visited.append(cur_n)
for next_n in graph[cur_n]:
indegrees[next_n] -= 1
if indegrees[next_n] == 0:
q.append(next_n)
return len(course_visited) == numCourses-
방문 여부를 확인하는
course_visited, 그래프graph, 들어오는 edge가 없는 vertex를 저장할indegress리스트를 구현한다. (indegress 기본값 = 0) -
graph 를 인접리스트를 통해 구현한다.
[a, b]인 경우, b가 선수과목이다. -
그래프를 생성하면서, 선수과목이 있는 과목들의
indegress를 +1씩 업데이트 해준다. -
indegress를 탐색하여 값이 0인 vertex들을 큐에 append 한다. -
while문을 통해 해당 vertex들을 방문하고, 방문한 vertex의
indegrees를 -1씩 업데이트 해준다. 그리고 이 값이 0인 경우 큐에 append 해준다. -
큐에 요소가 없을 때 까지 반복해준다.
-
course_visited의 길이와numCourses를 비교하여 값이 같으면 모든 노드를 방문한 것이므로True, 아니면False를 출력해준다.
⭐⭐⭐⭐⭐
- 위상정렬의 대표적인 예시 문제이다. indegress가 0인 노드들을 방문하면서 노드 개수와 비교를 통해 그래프 내에 사이클 유무를 확인할 수 있다.
