[백준]2623: 음악프로그램 - JAVA

[백준]2623: 음악프로그램

2623번: 음악프로그램

풀이

🪑 우선순위를 위배하지 않는 순서를 결정하는 문제! 위상정렬 문제이다.

 

📝 문제의 조건을 정리해 보자.

• 각각의 피디가 가져온 모든 우선순위를 만족하는 순서를 구해야 한다.
• 불가능할 경우 0을 출력한다.

 

🔧 구현 과정을 정리해 보자!

1. 정보를 입력받으며 진출간선 정보, 진입 간선의 수를 저장해 준다.
2. 위상 정렬을 하며 우선순위를 위반하지 않는 정렬 순서를 구한다.
3. 가능한 경우 구한 순서를 출력하고, 불가능한 경우 0을 출력한다.

 

🔹 진출간선 정보, 진입 간선의 수를 저장해 준다.

- 위상정렬 알고리즘을 사용하기 위해 필요한 정보들이다.

- 진출간선 정보는 N번째 다음으로 올 수 있는 가수의 정보를 의미한다.

- 진입 간선의 수는 N번 가수 이전에 와야하는 가수의 수를 의미한다.

 

🔹 위상 정렬로 정렬 순서를 구한다.

- 진입 간선의 수가 0인 가수를 차례대로 Queue에 담아준다.

- Queue에 담아주었으므로 해당 가수 다음으로 올 수 있는 가수들을 탐색하며 해당 가수들의 진입 간선의 수를 하나 줄여준다.

- 진입 간선의 수가 0이되는 가수가 있다면 Queue에 담아준다.

 

🔹 가능한 경우 구한 순서를 출력하고, 불가능한 경우 0을 출력한다.

- 순서를 구하는게 가능하다면 결과 리스트의 크기가 가수들의 수와 일치할 것이다.

 

코드

import java.util.*;
 
public class Main {
 
    static ArrayList<Integer>[] list;
    static int[] indegree;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        //입력
        int n = scan.nextInt();
        int m = scan.nextInt();
 
        list = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
 
        indegree = new int[n + 1];
        for(int i = 0; i < m; i++) {
            int count = scan.nextInt();
            if(count == 0) continue;
            int s = scan.nextInt();
            for(int j = 0; j < count - 1; j++) {
                int e = scan.nextInt();
                indegree[e]++;
                list[s].add(e);
                s = e;
            }
        }
        //입력 끝
 
        ArrayList<Integer> result = topologySort(n);
        if(result.size() == n)  {
            for(int i = 0; i < result.size(); i++) {
                System.out.println(result.get(i));
            }
        } else {
            System.out.println("0");
        }
    }
 
    public static ArrayList<Integer> topologySort(int n) {
        Queue<Integer> q = new LinkedList<>(); 
        for(int i = 1; i <= n; i++) {
            if(indegree[i] == 0) {
                q.offer(i);
            }
        }
 
        ArrayList<Integer> result = new ArrayList<>();
        while(!q.isEmpty()) {
            int current = q.poll();
            result.add(current);
 
            for(int i = 0; i < list[current].size(); i++) {
                int next = list[current].get(i);
                indegree[next]--;
                if(indegree[next] == 0) q.offer(next);
            }
        }
        return result;
    }
}