문제 풀이(56)

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

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



class Node implements Comparable<Node>{
    String name;
    PriorityQueue<String> data = new PriorityQueue<>();

    Node(String name, PriorityQueue<String> tmp)
    {
        this.name = name;
        data = tmp;
    }

    @Override
    public int compareTo(Node now)
    {
        return this.name.compareTo(now.name);
    }

    @Override
    public String toString()
    {
        return name+" "+data;
    }
}

public class Main {

    static int N,M;
    static HashMap<Integer, String>map = new HashMap<>();
    static HashMap<String, Integer>namToIndex = new HashMap<>();
    static ArrayList<Integer>[] adj;
    static int[] indegree;
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        adj = new ArrayList[N + 1];

        indegree = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= N; i++) {
            String name = st.nextToken();
            map.put(i, name);
            namToIndex.put(name, i);
            adj[i] = new ArrayList<>();
        }

        M = Integer.parseInt(br.readLine());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            String a = st.nextToken();

            String b = st.nextToken();

            int E  = 0;

            E = namToIndex.get(a);
           
            int S = 0;
           
            S = namToIndex.get(b);
          

            adj[S].add(E);

            indegree[E]++;

        }

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

        PriorityQueue<String>pq = new PriorityQueue<>();

        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                pq.offer(map.get(i));
                Q.offer(i);
            }
        }

        System.out.println(pq.size());

        while (!pq.isEmpty()) {
            System.out.print(pq.poll()+" ");
        }
        
        System.out.println();

        PriorityQueue<Node>data = new PriorityQueue<>();

      
        while (!Q.isEmpty()) {
            int now = Q.poll();
          
            for(int next : adj[now])
            {
                indegree[next]--;

                if (indegree[next] == 0) {
                    Q.offer(next);
                    pq.add(map.get(next));  
                }
            }

            data.add(new Node(map.get(now), pq));

            pq = new PriorityQueue<>();
        }

        while (!data.isEmpty()) {
            
            Node now = data.poll();

            System.out.print(now.name+" "+now.data.size()+" ");

            while (!now.data.isEmpty()) {
                System.out.print(now.data.poll()+" ");
            }

            System.out.println();
        }

        
    }
}

map, namToIndex: map은 정수 인덱스와 이름을 매핑하고, namToIndex는 이름과 인덱스를 매핑한다.
adj: 각 노드의 인접 노드 목록을 저장하는 배열이다.
indegree: 각 노드로 들어오는 엣지의 수를 저장하는 배열이다.

입력을 받아 각 변수를 초기화하고 의존성 관계를 구성한다.
indegree가 0인 노드, 즉 어떤 다른 노드에도 의존하지 않는 노드들을 큐 Q와 우선 순위 큐 pq에 추가한다.
indegree가 0인 노드들을 출력한다.
큐 Q에서 요소를 하나씩 꺼내어 그 요소의 인접 노드들의 indegree를 감소시킨다.
indegree가 0이 된 노드를 pq에 추가한다.
data 우선 순위 큐에 새로운 Node 객체를 추가한다. 이 때, pq는 현재 Node에 종속된 노드들을 포함하고 있다.
pq를 새로운 우선 순위 큐로 초기화하여 다음 반복을 준비한다.
코드의 마지막 부분에서 data 우선 순위 큐에서 Node 객체를 하나씩 꺼내고, 그 Node의 이름과 종속된 노드들의 수 및 이름을 출력한다.