728x90
위상 정렬은 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에서 노드 순서를 나열하는 알고리즘
즉, 어떤 일을 하기 위해 선행되어야 할 작업들이 있을 때, 그 작업 수행 순서를 결정
📌 사이클이 없는 방향 그래프여야만 위상 정렬 가능!
핵심 이론
위상 정렬은 다음가 같은 단계로 설명할 수 있음
- 각 노드의 진입 차수(in-degree)를 센다.
- 진입 차수가 0인 노드들을 큐에 넣는다.
- 큐에서 노드를 하나씩 꺼내어 결과에 넣고, 연결된 노드들의 진입 차수에서 1을 뺀다.
- 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다.
- 모든 노드를 처리하면 끝.
진입 차수 저장
1에서 2, 3을 가리키고 있으므로 D[2], D[3]을 각각 만큼 증가 (나머지 노드 동일)
진입 차수 0인 노드 처리
진입 차수가 0인 노드 1을 택해 위상 정렬 배열에 저장.
연결된 `2`, `3` 노드의 진입 차수 값 -1
👉 모든 노드가 위상 정렬 배열에 들어갈 때까지 반복
📌 진입 차수가 0인 노드가 여러 개인 경우, 무엇을 선택하느냐에 따라 다른 정렬 결과 도출
= 위상 정렬이 늘 같은 정렬 결과를 보장하지 않음!
관련 문제
[백준, 줄 세우기] https://www.acmicpc.net/problem/2252
728x90