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

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

 

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

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

---

1.  아이디어

 

이름을 통해 처리하는 상황이 많아서 Set, Map 등 다양한 자료구조를 활용했고 시조부터 위상 정렬을 수행해서 해결했다.

---

2. 문제풀이

 

자식, 자손, 진입차수를 Map 자료구조로 처리했다. 자식은 출력을 위해 TreeMap을 활용했고 value도 TreeSet으로 미리 정렬하도록 했다. 자식과 자손을 구부하는게 포인트인데 위상 정렬은 자손으로 수행하며 선행 노드의 제거로 후행 노드의 진입차수가 0이 된 순간이 부모와 자식 관계가 됨을 활용했다.

---

3. 코드

 

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        // 자식들을 저장하는 트리맵
        Map<String, TreeSet<String>> childrenMap = new TreeMap<>();

        // 자식 + 자손들을 저장하는 해시맵
        Map<String, List<String>> descendantMap = new HashMap<>();

        // 진입차수를 저장하는 해시맵
        Map<String, Integer> indegree = new HashMap<>();

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

            childrenMap.put(name, new TreeSet<>());
            descendantMap.put(name, new ArrayList<>());
            indegree.put(name, 0);
        }

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

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

            descendantMap.get(ancestor).add(descendant);
            indegree.put(descendant, indegree.get(descendant) + 1);
        }

        // 가문의 시조들을 저장하는 트리셋
        Set<String> root = new TreeSet<>();

        topologicalSort(root, childrenMap, descendantMap, indegree);

        String ans = print(root, childrenMap);

        bw.write(ans);
        bw.flush();
    }

    // 가문의 시조부터 수행하는 위상정렬
    private static void topologicalSort(Set<String> root, Map<String, TreeSet<String>> childrenMap, Map<String, List<String>> descendantMap, Map<String, Integer> indegree) {
        Queue<String> q = new ArrayDeque<>();

        for (Map.Entry<String, Integer> entry : indegree.entrySet()) {
            if (entry.getValue() == 0) {
                q.add(entry.getKey());
                root.add(entry.getKey());
            }
        }

        while (!q.isEmpty()) {
            String name = q.remove();

            for (String descendant : descendantMap.get(name)) {
                indegree.put(descendant, indegree.getOrDefault(descendant, 0) - 1);
                if (indegree.get(descendant) == 0) {
                    q.add(descendant);
                    childrenMap.get(name).add(descendant);
                }
            }
        }
    }

    // 출력용 메서드
    private static String print(Set<String> root, Map<String, TreeSet<String>> childrenMap) {
        StringBuilder sb = new StringBuilder();

        sb.append(root.size()).append("\n");

        for (String name : root) {
            sb.append(name).append(" ");
        }
        sb.append("\n");

        for (Map.Entry<String, TreeSet<String>> entry : childrenMap.entrySet()) {
            sb.append(entry.getKey()).append(" ").append(entry.getValue().size()).append(" ");

            for (String child : entry.getValue()) {
                sb.append(child).append(" ");
            }

            sb.append("\n");
        }

        return sb.toString();
    }

}

---

4. 후기