할 일 순서 정하기

문제: ORDERING / 그래프

[해결책 / 후기]

유명한 문제인 것 같다. 위상정렬이라는 것도 처음 알게 되었다.

내용은 일의 순서를 정하는 것. 문제 해결을 위해서 반드시 위상정렬을 이용해야 하는건 아닌 듯하다.

다음과 깉이 생각해볼 수 있겠다.

1. 작업을 그래프로 추상화

* 각 작업은 그래프에서 하나의 정점(vertice)이 된다. 

* 작업 A를 마치고 B를 한다는 것은 A에서 B로 가는 간선(edge)을 긋는 것이다.

* 이때 B의 입력차수는 1증가 한다. 입력 차수가 있다는 것은 이전에 처리해야할 작업이 있음을 의미한다.

2. 작업 순서

(1) 정점 사이에 간선을 긋는다.

(2) 입력 차수가 0인 작업들을 "우선순위 큐"에 넣는다. 

     그냥 큐를 사용하면 오답이 되는데, 문제에 "사전순"이라는 조건이 붙었기 때문이다.

     문제의 조건은 위상정렬 결과로 여러 조합이 나온다는 사실에 기인한다.

(3) 큐에서 작업을 하나씩 꺼낸다. 그리고 현재 작업을 끝내야 시작할 수 있는 작업들의 입력차수를 줄인다.

     이 과정에서 입력차수가 0이 되는 작업들을 큐에 넣는다.

(4) 큐가 빌때까지 (3)을 반복한다.

이런 순서로 처리하면 문제의 조건대로 처리할 수 있다.

코드: https://github.com/xgate/algospot/blob/master/GRAPH/ORDERING.cpp

[출처] [AOJ 문제] 할 일 순서 정하기|작성자 DevMoon