백준 2623 음악프로그램 Java [위상정렬]

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

2623번: 음악프로그램

 

위상 정렬을 사용해서 문제를 풀이했다

입력을 예시로 들면

3 1 4 3 일때

3은 뒤에 숫자니까 넘어가고 1 4 3을 각각 다음 나오는 숫자를 tree의 자식노드처럼 추가해뒀다

1의 자식노드 4, 4의 자식노드 3

자식노드를 추가할 때 자식노드들에 가중치를 1씩 줬다 

다음 입력들도 마찬가지로 과정을 반복하고나서

가중치가 0인 노드들부터 큐에 넣고

큐에서 한개씩 빼고 카운트하면서 bfs로 탐색하는데

자식노드의 가중치를 1씩 빼가면서 가중치가 0이 되면 큐에 넣어준다

큐에서 뺄 때 카운트를 하는 과정으로 모든 노드를 탐색했는지 확인 후

모두 돌았으면 방문한 노드들을 순서대로 담은 값을 출력해주면 된다

 

import java.io.*;
import java.util.*;

public class Main {
    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();
        Queue<Integer> queue = new LinkedList<>();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] degree = new int[N + 1];
        ArrayList<Integer>[] next = new ArrayList[N+1];
        for (int n = 1; n <= N; n++) next[n] = new ArrayList<>();
        for (int m = 0; m < M; m++) {
            int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int i = 2; i < arr.length; i++) {
                degree[arr[i]]++;
                next[arr[i-1]].add(arr[i]);
            }
        }
        for (int n = 1; n <= N; n++) {
            if (degree[n] == 0) {
                degree[n]--;
                queue.add(n);
            }
        }
        while (!queue.isEmpty()) {
            int now = queue.poll();
            sb.append(now).append("\n");
            N--;
            for (int i : next[now]) {
                degree[i]--;
                if (degree[i] == 0) queue.add(i);
            }
        }
        sb.setLength(sb.length() - 1);
        if (N != 0) System.out.println(0);
        else System.out.println(sb);
    }
}