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

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

 

이번 알고리즘은 위상정렬입니다. 위상 정렬은 그래프에서 방향을 가지는 간선으로 이루어져 있으며 사이클이 없는 것을 말합니다.

간단하게 설명을 하자면 A를 하기 위해서 B를 우선 해야 한다는 가정이 있다면 A, B와의 관계를 B -> A로 나타낼 수 있습니다.

 

문제에서는 위의 개념만 적용하면 바로 풀이를 할 수 있습니다. 서로의 관계를 M번 만큼 제시하는 것 말고는 크게 신경 써야 하는 부분은 없습니다. 우선 시 하는 것이 없는 것을 먼저 큐로 넣고 큐에서 나오면서 자신을 필요로 하는 정점을 가져오고 이 정점의 우선 시 하는 갯수에 -1을 하면 됩니다. 여기서 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 Backjoon_2623_음악프로그램 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N+1];
        ArrayList<Integer>[] lst = new ArrayList[N+1];

        for(int i = 1 ; i <=N ; i++){
            lst[i] = new ArrayList<>();
        }

        for(int i = 0 ; i < M ; i++){
            String[] str = br.readLine().split("\\s");
            int total = Integer.parseInt(str[0]);
            for(int j = 1 ; j < total ; j++){
                int V1 = Integer.parseInt(str[j]);
                int V2 = Integer.parseInt(str[j+1]);
                lst[V1].add(V2);
                arr[V2]++;
            }
        }

        Queue<Integer> q = new LinkedList<>();

        for(int i = 1 ; i <= N ; i++){
            if(arr[i] == 0) q.offer(i);
        }

        int count = 0;
        while(!q.isEmpty()){
            Integer poll = q.poll();
            sb.append(poll).append(" ");
            count++;
            for(int value : lst[poll]){
                arr[value]--;
                if(arr[value] == 0){
                    q.offer(value);
                }
            }
        }

        if(count == N){
            System.out.println(sb);
        }else{
            System.out.println(0);
        }
    }
}