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

문제풀이

 위상정렬을 활용한다. 이 문제에서는 위상정렬이 성립되지 않는 경우를 생각해야된다.

 

위상정렬이 이루어지는 조건은 노드가 다 출력될때까지 in-degree가 0이 아닌 노드가 없는 것인데 그거 말고 이상한 방법으로 사이클 체크를 하려해서 고생을 했다.

 

개념에 충실하자...

 

추가로 위상정렬을 간략하게 설명하자면

indegree가 0인 노드를 큐에다 추가하는 방식

프린트는 물론 큐에서 하나씩.

그러면 순서가 보장된다.

소스코드

 

import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Baekjoon2623 {
    static int N;
    static int M;
    static ArrayList<Integer>[] graph;
    static int[] countOfInDegree;
    static Queue<Integer> queue;
    static ArrayList<Integer> result = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        M = scan.nextInt();
        graph = new ArrayList[N+1];
        countOfInDegree = new int[N+1]; //초기값 0이라서 int배열
        queue = new LinkedList<>();
        initGraph(scan);
        for(int i=1;i<=N;i++){
            if(countOfInDegree[i]==0)
                queue.add(i);
        }
        if(queue.isEmpty()){
            System.out.println(0);
            return;
        }
        arrangeOrder();
        if(result.size()!=N)
            System.out.println(0);
        else {
            for (int num : result) {
                System.out.println(num);
            }
        }
    }
    public static void arrangeOrder() {
        while(!queue.isEmpty()){
            int node = queue.poll();
            result.add(node);
            for(int i=0;i<graph[node].size();i++){
                countOfInDegree[graph[node].get(i)]--;
                if(countOfInDegree[graph[node].get(i)]==0){
                    queue.add(graph[node].get(i));
                }
            }
            graph[node].clear();
        }
    }
    public static void initGraph(Scanner scan) {
        for(int i=1;i<=N;i++){
            graph[i] = new ArrayList<>();
        }
        for(int i=0;i<M;i++){
            int num = scan.nextInt();
            int from = scan.nextInt();
            int to =0;
            for(int j=1;j<num;j++){
                to = scan.nextInt();
                graph[from].add(to);
                countOfInDegree[to]++;
                from = to;
            }
        }
    }
}
 

문제 링크 : https://www.acmicpc.net/problem/2623

2623번: 음악프로그램