위상정렬

위상정렬이란 순서가 정해져 있는 작업을 차례로 수행하여야 할 때 순서를 결정해 주는 알고리즘이다.

백준의 2252번 문제를 보자

두 학생의 키를 비교하는 방법으로 줄을 세우는 문제이다.

그냥 A가 B보다 크다라는 것만 주어지고 키를 작은 순서대로 출력하는 문제이다.

A노드->B노드

 

예제를 그림으로 보면

이런식으로 나온다.

1이 3보다 키가 작고

2도 3보다 키가 작다.

그러면 답은 1,2,3 또는 2,1,3이 될 수 있다. 왜냐?? 1과 2에 대한 비교를 하지 않았기 때문에 누가 더 크고 작은 지를 구분할 수 없기 때문이다.(문제에서도 답이 여러 가지인 경우 아무거나 출력한다라고 명시해 놓았다.)

 

그래서 위상정렬이 무엇이냐!!

방향이 있는 그래프여야 하고 그래프는 사이클이 존재하지 않는 그래프에서 순서를 찾는 알고리즘이다.

무방향 그래프 XX 방향 그래프 OO 사이클 존재 XX

 

알고리즘 순서

1. 큐를 선언하고 진입차수를 관리하는 배열을 선언한다.

2. 진입차수를 관리하는 배열을 채워 넣는다.(1->3이면 arr[3]++하고 2->3이면 arr[3]++한다. 후순위에 진입차수를 더해준다.)

3. 진입차수가 0인 노드를 큐에 넣는다.

4. 큐에서 하나를 pop하고 그 노드와 인접한(그 노드가 가르키는) 노드의 진입차수를 1 감소시킨다.(만약 감소된 노드의 진입차수가 0이면 큐에 넣음.)

5. 큐가 빌 때까지 3,4를 반복한다.