[ 백준 / 자바 ] 2623. 음악프로그램

 

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

2623번: 음악프로그램

---

---

📑 문제

음악 프로그램에 N명의 가수가 출연하는데, 이 가수들의 출연 순서를 정해야 한다.

보조 피디 M명은 각자 순서를 정해온다.

이를 취합해 최종 순서를 정해야 하는데, 경우에 따라 순서를 정하는 것이 불가능 할 수도 있다. (사이클이 도는 경우)

순서를 정할 수 있다면 순서를 출력하고, 정할 수 없다면 0을 출력하는 문제.

 

💡 입력

✔ 첫째줄에 가수의 수 N, 보조PD의 수 M 제시

✔ 1 ≤ N ≤ 1,000

✔ 1 ≤ M ≤ 100

✔ 둘째줄부터 각 보조PD가 정한 순서들이 한줄씩 제시

✔ 각 줄의 맨앞 ⇒ 보조피디가 담당한 가수의 수 / 그 뒤로는 보조PD가 정한 가수 순서

 

---

---

✨ 풀이과정

✔ 위상정렬만을 활용하여 풀 수 있는 문제

✔ 사이클이 돌면 반드시 모든 노드를 돌지 못하고 while문이 종료돼 중간에 끊기고 만다

⇒ inDg 배열에 사용하지 못한 노드들 찌꺼기가 남아있음

✔ 이 찌꺼기가 있는지 없는지를 판단하여 정답을 출력한다

 

---

---

📑 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class G3_2623_음악프로그램 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); //가수의 수
		int M = sc.nextInt(); //보조PD의수
		
		List<Integer> adj[] = new ArrayList[N];
		for(int i=0; i<N; i++) adj[i] = new ArrayList<>();
		
		int[] inDg = new int[N];
		
		for(int i=0; i<M; i++) {
			int S = sc.nextInt(); //보조피디가 담당한 가수의 수
			int[] singer = new int[S];
			
			for(int j=0; j<S; j++) {
				singer[j] = sc.nextInt();
			} //가수 입력받기
			
//			System.out.println(Arrays.toString(singer));
			for(int j=0; j<S-1; j++) { //리스트에 연결하기 위해 가수배열을 돌아봅시다
				int st = singer[j]-1; //인덱스에 맞게 -1씩 해주기
				int ed = singer[j+1]-1;
				
				adj[st].add(ed); //인접리스트로 연결
				inDg[ed]++; //정점에 간선 연결됐다고 체크
			}
		}
		
		Queue<Integer> q = new LinkedList<>();
		
		for(int i=0; i<N; i++) {
			if(inDg[i] == 0) q.add(i);
		}
		
		int[] musicShow = new int[N];
		int idx = 0;
		while(!q.isEmpty()) { //q가 빌 때까지 돌자
			int singer = q.poll(); // 가수 빼기
			musicShow[idx++] = singer; //출연자리스트에 가수 담기
			
			for(int i=0; i<adj[singer].size(); i++) { //연결돼있는 리스트만큼 돌기
				int num = adj[singer].get(i);
				inDg[num]--;
				
				if(inDg[num] == 0) q.add(num);
				
			}
		}
		
		//사이클이 돌면 inDg배열에 0이 아닌 숫자가 들어있음
		int cnt=0;
		for(int i=0; i<N; i++) {
			if(inDg[i]==0) cnt++;
		}
		

		if(cnt == N) { //사이클이 돌지 않고 위상정렬이 제대로 되었다면
			for(int i=0; i<N; i++) {
				System.out.println(musicShow[i]+1); //원래 노드 번호로 원상복구 시켜서 출력
			}
		} else {
			System.out.println(0); //사이클이 돌았을 땐 0 출력
		}
		
	} //main

}