8. 위상정렬(Topological sort)

Directed Acyclic Graph(DAG)

간선에 방향성이 있고, cyclic이 없는 graph(V +E)

차수 Degree, InDegree와 outDegree로 구별

정점들을 위상에 맞춰 정렬한다.

제일 먼저 올 수 없는 정점이 들어오는 간선이 없는 정점임에 집중할 수 있다.

하나씩 정렬시키면서 그래프에서 삭제하자.

 

정리

정점들의 indegree 계산하기

들어오는 간선이 0 개인 정점들을 찾아서 Queue에 넣고

Queue가 빌 때 까지

 1. 원소X를 꺼내서 "정렬" 시키기

 2. graph에서 정점 X 제거하기

 3. 새롭게 정렬 가능한 점 찾아서 D에 넣기.

Indegree계산은 O(|E|)

총 시간 복잡도는 O(|V| + |E| )

 

방향성에 따라 어떻게 그래프를 구성하고 설계할것이냐가 중요한것 같다.

필요하다의 개념과 충족한다의 개념으로 나누어 한가지를 선택해서 보아야하는데

dp적 관점으로 문제를 풀수도 있다. 순서대로 진행하기 때문에

결국 위상'정렬' 이지만 탐색과 결이 같다. (조건부 탐색이라고 할 수 있겠다)'

ㅇㅇ Point 는 dp적관점으로 볼 수 있다는 것과/ 필요하다 충족한다/ 순서가 있다

정도로 생각할 수 있을 것 같다.

 

Q1005 2637 ( 백준)

추천 문제)

백준 ACM Craft - https://www.acmicpc.net/problem/1644

백준 줄 세우기 - https://www.acmicpc.net/problem/2252

장난감 조립 - https://www.acmicpc.net/problem/2637