bj2623(음악 프로그램)-위상 정렬

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

 

이 문제는 위상 정렬만 알고 있다면 매우 쉽게 풀 수 있는 문제이다.

위상정렬은 네개의 자료구조를 가져야 한다.

1. 그래프 : 그래프로 추적하기 위함

2. visited : 순환을 확인하기 위함

3. entries : 진입 엣지 수를 체크하기 위함

4. 큐 : 순서를 배정해줘야하는 놈들을 모아두기 위함

 

노드 접근 시 진입 엣지를 하나 뺸다.

진입엣지 수가 0인 놈들을 큐에 집어넣는다.

큐가 빌 때까지 하나씩 꺼내며, answers에 포함하고(이게 정답이 된다.)

추적된 노드의 진입 엣지 수를 하나씩 뺴준다.

다시 큐에 집어넣는다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M;
    static boolean cant;
    static int[] entries;
    static boolean[] visited; //순환이 있을 시, 다시 방문할 것이다.
    static List<Integer> answers = new ArrayList<>();
    static List<Integer>[] graph;
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        solve();
        if(cant){
            System.out.println(0);
        }else{
            for(int answer : answers){
                System.out.println(answer);
            }
        }
    }

    private static void solve() {
        Queue<Integer> queue = new ArrayDeque<>();
        for(int i = 1; i <= N; i++){
            if(entries[i] == 0)queue.add(i);
        }
        topologySort(queue);
        for(int i = 1; i < N; i++){
            if (entries[i] != 0) {
                cant = true;
                break;
            }
        }
    }

    private static void topologySort(Queue<Integer> queue) {
        while(!queue.isEmpty()){
            int temp = queue.poll();
            answers.add(temp);
            for(int next : graph[temp]){
                entries[next]--;
                if(visited[next]){
                    cant = true;
                    return;
                }
                if (entries[next] == 0) {
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }

    private static void initialize() throws IOException {
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());
        entries = new int[N+1];
        visited = new boolean[N+1];
        graph = new ArrayList[N+1];
        for(int i = 1; i <= N; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 0; i < M; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int cnt = Integer.parseInt(stringTokenizer.nextToken());
            int prev = Integer.parseInt(stringTokenizer.nextToken());
            for(int j = cnt; j > 1; j--){
                int curr = Integer.parseInt(stringTokenizer.nextToken());
                graph[prev].add(curr);
                entries[curr]++;
                prev = curr;
            }
        }
    }
}