[백준] 2623. 음악프로그램 (Java)

[BOJ] 2623. 음악프로그램

📌 풀이 과정

위상정렬 알고리즘 !!

문제에서 여러 가수들의 공연하는 순서를 결정해야 한다.
하지만 보조 PD들이 정해둔 가수들 사이의 순서 조건에 성립하도록 해야하므로 위상 정렬 알고리즘을 사용해야 한다.

위상 정렬 구현

1. 진입 차수가 0인 정점(시작 정점)를 큐에 모두 넣는다.

2. 큐에서 진입 차수가 0인 정점을 꺼내어 자신과 인접한 정점의 간선을 제거한다.
   → 인접한 정점의 진입 차수를 1 감소시킨다.

3. 간선 제거 후 진입 차수가 0이 된 정점을 큐에 넣는다.

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int N, M;
	static int[] inDegree;
	static ArrayList<Integer>[] turn;
	static ArrayList<Integer> answer = new ArrayList<>();
	
	static void topology() {
		Queue<Integer> q = new LinkedList<>();
		
        for(int i = 1; i <= N; i++) {
        	if(inDegree[i] == 0) q.offer(i);
        }
        
        while(!q.isEmpty()) {
        	int cur = q.poll();
        	answer.add(cur);
        	
        	for(int i = 0; i < turn[cur].size(); i++) {
        		int next = turn[cur].get(i);
        		inDegree[next] -= 1;
        		
        		if(inDegree[next] == 0) q.offer(next);
        	}
        }
	}

	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken()); // 가수의 수
        M = Integer.parseInt(st.nextToken()); // 보조 PD의 수
        inDegree = new int[N + 1];
        turn = new ArrayList[N + 1];
        
        for(int i = 1; i <= N; i++) {
        	turn[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int count = Integer.parseInt(st.nextToken()); // 보조 PD가 정한 가수의 수
            
            
            int[] sequence = new int[count];
            for (int j = 0; j < count; j++) {
                sequence[j] = Integer.parseInt(st.nextToken()); // 가수 번호
            }

            for (int j = 0; j < count-1; j++) {
                int n1 = sequence[j]; // 가수 번호
                int n2 = sequence[j+1]; // 가수 번호
                turn[n1].add(n2); // n1 -> n2 순서
        		inDegree[n2]++;
            }
        }
        
        topology();
        
        if(answer.size() == N) {
        	for(int n : answer) {
    			System.out.println(n);
    		}
        }
        else {
        	System.out.println(0);
        }
        
	}

}