문제 1030 · 중급 6
배포 순서 정하기
그래프 · 위상 정렬 · 우선순위 큐
테스트별 제한 2000ms · 브라우저 채점
문제
마이크로서비스 N개(1번 ~ N번)를 새 서버에 하나씩 배포해야 한다. 'a 를 배포한 뒤에야 b 를 배포할 수 있다' 는 의존 관계가 M개 있다. 배포 담당자는 매번 '지금 배포할 수 있는 서비스(의존하는 서비스가 모두 배포된 서비스)' 중 번호가 가장 작은 것을 배포한다. 이 방식으로 정해지는 배포 순서를 구하라. 의존 관계가 순환해서 모든 서비스를 배포할 수 없으면 -1 을 출력한다.
입력
첫째 줄에 N 과 M 이 주어진다. (1 ≤ N ≤ 20,000, 0 ≤ M ≤ 40,000) 다음 M개 줄에 a 와 b 가 주어진다. a 를 b 보다 먼저 배포해야 한다는 뜻이다. (1 ≤ a, b ≤ N, a ≠ b) 같은 관계가 여러 번 나올 수 있다.
출력
배포 순서를 공백으로 구분해 한 줄에 출력한다. 불가능하면 -1 을 출력한다.
예제 입력 1
5 4 3 1 3 2 1 4 5 4
예제 출력 1
3 1 2 5 4
예제 입력 2
3 3 1 2 2 3 3 1
예제 출력 2
-1
힌트 펼치기
- 서비스마다 '아직 배포되지 않은 선행 서비스 수(진입 차수)' 를 세어 두고, 0 이 된 서비스를 후보로 둔다.
- 후보 중 번호가 가장 작은 것을 매번 꺼내야 하므로 후보를 우선순위 큐(최소 힙)에 넣자. 끝까지 N개를 못 꺼내면 순환이 있는 것이다.
관련 장
풀이 작성
코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.