[BaekJoon] 21276 계보 복원가 호석 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int familyCnt; // 사람 수
    static int relationCnt; // 기억하는 정보의 개수
    static Map<String, Integer> ancestorNum; // 각 사람들의 조상의 수를 나타내는 map
    static Map<String, List<String>> descendants; // 각 사람의 자손들을 나타내는 map
    static Map<String, List<String>> answer; // 각 사람의 자식들을 나타내는 map

    static void input() {
        Reader scanner = new Reader();

        familyCnt = scanner.nextInt();
        answer = new HashMap<>();
        descendants = new HashMap<>();
        ancestorNum = new HashMap<>();

        for (int idx = 0; idx < familyCnt; idx++) {
            String family = scanner.next();
            answer.put(family, new ArrayList<>());
            ancestorNum.put(family, 0);
            descendants.put(family, new ArrayList<>());
        }

        relationCnt = scanner.nextInt();
        for (int relation = 0; relation < relationCnt; relation++) {
            String startFamily = scanner.next();
            String endFamily = scanner.next();
            descendants.get(endFamily).add(startFamily);
            ancestorNum.put(startFamily, ancestorNum.get(startFamily) + 1);
        }
    }

    /*
     * 자신의 자식들을 찾아야 하는데, 이는 위상 정렬을 하는 것과 같다
     *  - 자신의 바로 아래 순위에 해당하는 사람들이 자신의 자식이 된다
     *
     * 위상 정렬
     *  1. 조상의 수가 0인 사람들을 찾아 Queue에 넣는다
     *      - 조상의 수가 0이라는 것은 자신이 가문의 시조임을 의미한다
     *  2. Queue에 있는 사람들을 하나씩 순회하며 자신의 자식을 찾는다
     *      - 현재 사람의 자손들을 순회하며 각 자손들의 조상의 수를 1 빼준다
     *          - 현재 사람은 순위가 정해져있기 때문에 1을 빼준다
     *      - 조상의 수를 1 뺐을 때 각 자손의 조상의 수가 0이라면 이 자손도 순위가 정해지므로 Queue에 자손을 넣고 현재 사람의 자식으로 현재 자손을 추가한다
     *      - 위 과정을 Queue가 빌 때까지 진행하며 각 사람의 자식을 찾는다
     */
    static void solution() {
        topologicalSort();
        List<Map.Entry<String, List<String>>> entryList = sort();
        print(entryList);
    }

    static void print(List<Map.Entry<String, List<String>>> entryList) {
        for(Map.Entry<String, List<String>> entry : entryList) {
            sb.append(entry.getKey()).append(' ');
            sb.append(entry.getValue().size()).append(' ');
            Collections.sort(entry.getValue());
            for(String descendant : entry.getValue()) {
                sb.append(descendant).append(' ');
            }
            sb.append('\n');
        }

        System.out.print(sb);
    }

    static List<Map.Entry<String, List<String>>> sort() {
        List<Map.Entry<String, List<String>>> entryList = new ArrayList<>(answer.entrySet());
        Collections.sort(entryList, new Comparator<Entry<String, List<String>>>() {
            @Override
            public int compare(Entry<String, List<String>> o1, Entry<String, List<String>> o2) {
                return o1.getKey().compareTo(o2.getKey());
            }
        });

        return entryList;
    }

    static void topologicalSort() {
        Queue<String> queue = new LinkedList<>();
        List<String> fathers = new ArrayList<>();
        for(String family : ancestorNum.keySet()) {
            if(ancestorNum.get(family) == 0) {
                fathers.add(family);
                queue.offer(family);
            }
        }

        sb.append(fathers.size()).append('\n');
        Collections.sort(fathers);
        for(String father : fathers) {
            sb.append(father).append(' ');
        }
        sb.append('\n');

        while(!queue.isEmpty()) {
            String curFamily = queue.poll();

            for(String descendant : descendants.get(curFamily)) {
                ancestorNum.put(descendant, ancestorNum.get(descendant) - 1);
                if(ancestorNum.get(descendant) == 0) {
                    answer.get(curFamily).add(descendant);
                    queue.offer(descendant);
                }
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}