위상정렬, DAG(Directed Acyclic Graph)

그래프의 분류 중 하나로 DAG,사이클이 없는 방향그래프가 있다. DAG에서는 항상 위상정렬이 가능하고 그 후에 동적 계획법을 적용하는 것이 가능하다.

 

<동적계획법?>

ㅁ 정점u에서 정점v로 가는 최단/최장 경로는 무엇인가?

ㅁ 경로 중 간선의 개수가 가장 적은/많은 경우 간선은 몇 개인가?

ㅁ 모든 경로에 포함된 정점은 어떤 것이 있는가?

ㅁ 서로 다른 경로의 개수는 몇 개인가?

등등.. 위상정렬된 순서대로 처리하면 구할 수 있다.

 

또한 모든 동적 계획법 문제는 DAG로 나타낼 수 있다. 이 때 정점은 dp상의 상태에, 간선은 상태간의 관계에 대응된다.

ex)동전문제, 냅색..

 

 

<방법1>

사이클이 없는 그래프에서 정점의 탐색이 끝난 순서 (fin[u]=true)의 반대 순서로 처리하면 위상정렬 순서

(예)https://suuntree.tistory.com/manage/posts/

 

 

<방법2>

진입차수가 0인 정점들에 대해서 큐에 넣어서 처리한다. 다음 정점과 간선을 끊어주며 진행한다.

 

multisource bfs와 유사하다.

 

필요한 것:

 queue<int> q

 vector<int> adj[MAX]

 int ind[MAX] = {0}

//ind는 간선을 입력받을 때 적절히 초기화 해 준다.

queue<int> q;

for(int i=0; i<n; i++)
	if(ind[i]==0) q.push(i);
    
int cnt=0;    
while(!q.empty()){
    int curr = q.front();
    q.pop();
    cnt++;
    
    for(int next : adj[curr])
    	if(--ind[next]==0) q.push(next);
}

//cnt<n인 경우 위상정렬에 실패한 것. 사이클이 발생했을 수 있다.

    

result배열을 만들고,  result[cnt] = curr 문장을 추가하면 정점의 방문 순서를 알 수 있다.

 

기본문제:

https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

---