문제 이해

M명의 보조 PD가 가수의 순서를 정한다.

모든 보조 PD가 정한 가수의 순서를 지킬 수 있는 경우, 그 순서를 출력한다. 이 때, 답이 여러개 존재하면 아무거나 하나만 출력한다.
만일 경우의 수가 존재하지 않을 경우, 0을 출력한다.

---

문제 풀이

가수의 순서라고 했지만, 줄 세우기 문제처럼 "키"와 비슷한 문제라고 생각한다.
단지, 이 문제의 경우 키와는 달리 Cycle에 대한 처리가 추가되어야만 한다.

키가 A > B일 경우, A > B > A일 수는 없다.
하지만, 한 피디가 A ⇒ B로, 다른 피디가 B ⇒ A로 순서를 정할 수도 있다.

이 경우 문제는 모든 피디가 정한 순서를 지켜야 하기 때문에 Cycle이 발생하므로, 이 부분에 대한 처리가 필수적으로 필요하다.

만약 답이 존재할 경우, 이 그래프는 DAG일 것이므로, 위상 정렬 + Cycle 발견 로직을 추가하면 될 것이다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N,M;
	static ArrayList<Integer>[] lists;
	static int[] input;
	
	static void sort() {
		Queue<Integer> queue = new LinkedList<>();
		
		for(int i =1;i<N+1;i++) {
			if(input[i]==0) { // input이 0인 node들을 queue에 입력
				queue.add(i);
			}
		}
		
		ArrayList<Integer> ans = new ArrayList<>();
		
		while(!queue.isEmpty()) {
			int tmp = queue.poll();
			
			ans.add(tmp);
			
			for(int s:lists[tmp]) {
				input[s]--;
				if(input[s]==0) queue.add(s);
			}
		}
		
		 if (ans.size() == N) {
	            for (int x: ans) sb.append(x).append('\n');
		 }
	     else sb.append(0);
         /*
         Cycle이 이루어지는 상황을 살펴보자. A -> B -> A라고 가정하자.
         이 때, A는 input값이 B에 의해 최소 1을 가지고, 
         B도 A에 의해 input 값이 최소 1은 된다.
         
         즉, A와 B 모두 둘 중 하나가 없어지기 전에는 최소 1 값을 가지므로, 
         Queue에 포함될 수 없다.
         Queue에 한번이라도 포함되어야만 ans에 들어올 수 있기 때문에, 
         만약 ans의 size가 N이 아니라면 특정 Node는 Queue에 들어온 적이 없다는 
         의미이며, 이는 Cycle이 존재한다는 결론으로 귀결된다.
         */
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		M = sc.nextInt();
		lists = new ArrayList[N+1];
		input = new int[N+1];
		
		for(int i =1;i<N+1;i++) {
			lists[i] = new ArrayList<>();
		}
		
		for(int i =0;i<M;i++) {
			String tmp = sc.nextLine();
			String[] split = tmp.split(" ");
			
			for(int j =2;j<split.length;j++) {
				int start = Integer.parseInt(split[j-1]);
				int end = Integer.parseInt(split[j]);
				
				if(!lists[start].contains(end)) {
					lists[start].add(end);
					input[end]++; 
                    // PD는 A -> B -> C...순으로 순서를 정하므로, 
                    // list[A]의 원소로 B를 넣는다.
                    // 또한 A -> B이므로, B의 input값에 1을 더해
				}
			}
		}
		sort();
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2,3,4번째 줄 틀렸습니다 : Cycle 판단 여부 알고리즘을 잘못 구현하여 틀렸다.