Day-16 위상 정렬

---

1. 위상 정렬

• 위상 정렬(topology sort)는 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
• 시간 복잡도는 O(노드 수 + 에지 수)이다.
• 항상 같은 값으로 정렬되지 않는다. (결과가 다를 수 있음)

---

2. 위상 정렬 과정

1. 자기 자신을 가리키는 에지의 개수를 나타낸 진입 차수 배열을 생성
2. 진입 차수가 0인 노드를 선택하고 정렬 배열에 저장
3. 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 감소
4. 모든 노드가 정렬 배열에 저장될 때까지 과정 2, 3을 반복

---

3. 예제 문제

[2252] 줄 세우기 (JAVA)

[1516] 게임 개발 (JAVA)

---

[1766] 문제집 (JAVA)