DAG(Directed Acyclic Graph)는 사이클이 존재하지 않는 유향 그래프를 의미한다. 정의는 이렇게 간단하지만 응용할 수 있는 분야는 상당히 넓은 편이며, 최근에는 블록체인에서도 많이 다루면서 점점 주목받고 있는 개념이기도 하다. 사회과학에서도 등장한다고 한다.
그래프 이론의 관점에서 DAG의 큰 특징은 다음과 같이 나타낼 수 있다.
- 진입 차수가 $0$인 정점이 하나 이상 존재한다.
- 진출 차수가 $0$인 정점이 하나 이상 존재한다.
- 어떤 정점 및 그 정점과 연결된 간선들을 그래프에서 제거할 경우 남는 정점과 간선들로 이루어진 그래프도 DAG이다.
- 모든 정점을 순서대로 나열했을 때 간선의 방향이 전부 동일하게(왼쪽 → 오른쪽 또는 오른쪽 → 왼쪽) 할 수 있다.
네 번째 특징에 나온 정점 나열은 위상 정렬이라고 불리며 DAG와 연관되어 가장 많이 등장하는 주제 중 하나이다. 위상 정렬은 별도의 글에서 설명하며 여기서는 자세한 설명을 생략한다.
PS에서는 DAG의 개념이 단독으로 등장하는 문제는 찾아보기 어렵고, DAG에서 위상 정렬을 하는 문제나 그래프의 정점들을 SCC로 묶어서 DAG를 만들고 뭔가를 하는 문제 등 다른 개념이 결합된 문제들이 주로 등장한다. 위상 정렬과 SCC 등은 아직 설명하지 않은 내용이므로 해당 개념을 설명할 때 DAG와 결합된 문제를 함께 소개할 예정이며, 여기서는 DAG와 DFS, DP가 결합된 문제를 소개한다.
[참고 링크]
[연습문제]
BOJ 1005. ACM Craft (Gold III)
더보기
모든 간선을 뒤집은 다음 진입 차수가 $0$인 정점들에서 DFS를 차례로 실행하면서 정점들의 DP 테이블을 갱신한다. DP 테이블에는 각각의 건물을 건설하기까지 걸리는 최소 시간을 저장한다. 이런 유형의 문제들을 DAG DP라고 부르기도 한다.
'Algorithm > H. Trees & Graphs' 카테고리의 다른 글
| 124. Disjoint Set & Union-Find (0) | 2022.06.21 |
|---|---|
| 123. Topological Sorting (0) | 2022.04.30 |
| 121. Independent Set & Clique (0) | 2022.04.25 |
| 120. Dial's Algorithm (0) | 2022.03.09 |
| 119. 0-1 BFS (0) | 2022.03.07 |
