위상 정렬. [16169]

[1. 문제 설명]

n 개의 컴퓨터로 이루어진 시스템이 있고, 

이 시스템의 동작 체계가 정의되어 있을 때

임무 수행이 끝날 때 까지 걸린 시간을 구한다.

 

동작 체계는 아래를 참조

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

---

[2. 풀이 접근]

전체적인 풀이는 아래 문제와 유사하다.

https://testkernelv2.tistory.com/390

 

다만 몇 가지 다른 것은

본 문제에서는 선행관계를 직접 찾아서 만들어야 한다는 것이다.

전송시간까지 고려해야 한다는 것이다.

 

그림1. 계급, 컴퓨터 번호

==> 선행 관계 생성

1. 그림1과 같이 계급 순으로 정렬한다.
   (동작 체계 조건 중, 인접한 계급의 차이는 0 아니면 1이다.)
2. offset 배열을 생성한다.
   => ex) {0, 3, 4, 6, 7}
   [0, 3) 이 한 계급 그룹,
   [3, 4) 가 한 계급의 그룹...
3. 인접한 그룹 별로 선행 관계를 생성한다.
   => 위상 정렬을 위한 단방향 그래프 생성
   => 바로 인접한 것 끼리만 생성하면 된다.

이제 위상 정렬을 진행하면서 

각 컴퓨터가 동작을 시작하는 최대 시간을 갱신해나가면 된다.

 

동작 조건 중 이전 계급의 모든 컴퓨터가 작업을 종료해야만

다음 계급의 컴퓨터가 동작을 시작 할 수 있기 때문이다.

---

[3. 코드]