[Java] 백준 21276번: 계보 복원가 호석

[문제 바로 가기] - 계보 복원가 호석

유형 : 위상 정렬

💡 아이디어

주어지는 정보는 X의 조상 중 Y가 있다이므로 시조가 누구인지, 직계 자식은 누구인지 따로 구분해주어야 한다. 따라서 위상 정렬을 사용하면 좋다. (잊고 있던 위상 정렬의 개념을 이 포스트를 다시 읽고 이해했다.)

먼저 직계 자식의 구분 없이 일단 graph map에 넣어주었다. buildIndegree()에서 차수를 계산해서 시조를 따로 roots 리스트에 저장해주었다.

이후 BFS를 돌면서 차수를 하나씩 빼주었다. 이때 뺀 차수가 0인 경우 parent의 직계 자식이라는 뜻이므로 자식만 저장하는 map children에 저장해주었다.

풀이

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

public class Main {
    static Map<String, Set<String>> graph = new HashMap<>(); // 자손 담을 map
    static Map<String, Integer> indegree = new HashMap<>(); // 차수 저장할 map
    static Map<String, List<String>> children = new HashMap<>(); // 자식만 담을 map

    static List<String> names = new ArrayList<>(); // 이름 리스트
    static List<String> roots = new ArrayList<>(); // 시조 리스트

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            String name = st.nextToken();

            names.add(name);
            graph.put(name, new HashSet<>());
            children.put(name, new ArrayList<>());
        }

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

            String child = st.nextToken();
            String parent = st.nextToken();
            graph.get(parent).add(child);
        }

        buildIndegree();
        solve();
        print();
    }

    /**
     * 차수 계산 메서드
     */

    static void buildIndegree() {
        for (String name : names) indegree.put(name, 0);

        for (String parent : graph.keySet()) {
            for (String child : graph.get(parent)) {
                indegree.put(child, indegree.get(child) + 1);
            }
        }

        for (String name : names) {
            if (indegree.get(name) == 0) roots.add(name); // 시조 저장
        }

        Collections.sort(roots);
    }

    /**
     * 위상 정렬 메서드
     */

    static void solve() {
        Queue<String> q = new ArrayDeque<>();
        for (String root : roots) q.offer(root);

        while (!q.isEmpty()) {
            String parent = q.poll();

            for (String child : graph.get(parent)) {
                indegree.put(child, indegree.get(child) - 1);

                if (indegree.get(child) == 0) {
                    children.get(parent).add(child);
                    q.offer(child);
                }
            }
        }
    }

    /**
     * 출력 메서드
     */

    static void print() {
        StringBuilder sb = new StringBuilder();

        // 시조 root 출력
        sb.append(roots.size()).append("\n");
        for (String r : roots) sb.append(r).append(" ");
        sb.append("\n");

        // 이름 정렬 후 각각 직계 자식 출력
        Collections.sort(names);

        for (String name : names) {
            List<String> list = children.get(name);
            Collections.sort(list);

            sb.append(name).append(" ").append(list.size());
            for (String child : list) sb.append(" ").append(child);
            sb.append("\n");
        }

        System.out.print(sb);
    }
}