[그래프] DAG & 위상 정렬

📌 DAG(Directed Acyclic Graph)

방향 사이클이 없는 방향 그래프
예시) 작업들의 우선순위

📌 용어

Incoming : 들어오는 Edge
Indegree : 들어오는 Edge 개수 (진입간선)
Outcoming : 나가는 Edge
Outdegree : 나가는 Edge 개수 (진출간선)

📌 위상 정렬(Topology Sort)

DAG이어야 한다. → 방향 그래프, 사이클 x
indegree & outdegree로 구분
모든 정점에 연결된 간선을 한 번씩 보게 된다. 시간 복잡도는 O(V + E)

로직

1.
정점들의 Indegree[1~N]을 계산한다. (들어오는 간선 개수) → O(E)
2.
들어오는 간선(Indegree)이 0개인 정점들을 찾아, Q에 넣는다. → O(V)
Queue<Integer> q = new LinkedList<>(); for (int i = 1; i <= N; i++) { if (indegree[i] == 0) q.offer(i); }
Java
3.
Q가 빌때까지 순회한다. → O(V + E)
a.
D에서 꺼낸 x를 "정렬"시킨다. (결과 저장하기)
b.
Graph에서 정점 x를 "제거"한다.
c.
"새롭게 정렬 가능한 점"을 찾아, Q에 넣는다.
while(!q.isEmpty()) { int x = q.poll(); result.add(x); //3-1 정렬 for (int next : adj.get(x)) { //3-2 제거 if (--indegree[next] == 0) q.offer(next); } }
Java

📌 관련 문제

BOJ2623 - 음악 프로그램
BOJ9470 - Stahler 순서
BOJ14676 - 영우는 사기꾼?
BOJ1516 - 게임 개발
BOJ2056 - 작업
BOJ2637 - 장난감 조립

📌 참고 자료

TOP