[JAVA] 백준 21276번 【G2.계보 복원가 호석】

문제

21276번: 계보 복원가 호석

 

풀이

1️⃣ 위상 정렬과 우선순위 큐를 활용한 풀이

💡 떠오른 Idea

이 문제에서 가장 중요한 포인트는 직계 자손임을 어떻게 파악하는가였다.


haeun doha
doha minji
haeun minji

위와 같이 관계가 주어졌을 때

하은은 도하와 민지의 자손이고
도하는 민지의 자손임을 알 수 있는데

들어오는 간선의 수를 보면
 
민지 : 0
도하 : 1
하은 : 2
임을 알 수 있다.

위상 정렬에 따라 정렬하면 민지에서 시작해서 민지와 연결된 간선을 지우게 되는데

그러면

위와 같이 되고 간선의 수가


민지 : 0
도하 : 0
하은 : 1
임을 알 수 있다.

즉, 연결된 간선을 지웠을 때, 0이 되는 자손은 직계 자손이 됨을 알 수 있다.

이 개념과 위상 정렬을 사용하면 쉽게 해결할 수 있는 문제였다.

그리고 사전 순으로 정렬하는 과정이 필요하기 때문에, List로 데이터를 입력받아서 sort 를 사용해도 되긴 하지만

단순 사전 순 정렬이므로 우선순위큐를 이용하였다.

public class Main {

    // 계보 상 자식 관계 모두 저장
    static Map<String, List<String>> relation = new HashMap<>();

    // 직계 자손만 저장
    static Map<String, PriorityQueue<String>> directChildren = new HashMap<>();

    // 각 사람 별 간선이 오는 개수 저장
    static Map<String, Integer> indegree = new HashMap<>();

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

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < input.length; i++) {
            String name = input[i];
            relation.put(name, new ArrayList<>());
            directChildren.put(name, new PriorityQueue<>());
            indegree.put(name, 0);

        }

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

        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            String young = input[0];
            String old = input[1];
            // 계보 상 자식(직계인지 아닌지는 모름) 추가
            relation.get(old).add(young);

            // 자식들은 inDegree 값 증가
            indegree.put(young, indegree.get(young) + 1);
        }
        StringBuilder ans = new StringBuilder();

        Queue<String> q = new LinkedList<>();
        PriorityQueue<String> pq = new PriorityQueue<>();
        int K = 0;
        for (String name : indegree.keySet()) {
            // 들어오는 간선이 없다는 것은 최고 조상이라는 의미
            if (indegree.get(name) == 0) {
                K++;
                pq.offer(name);
                q.offer(name);
            }
        }
        ans.append(K + "\n");

        while (!pq.isEmpty()) {
            ans.append(pq.poll() + " ");
        }
        ans.append("\n");

        // 위상 정렬
        while (!q.isEmpty()) {
            String parent = q.poll();
            List<String> children = relation.get(parent);
            for (String child : children) {
                int n = indegree.get(child);
                // 간선이 1개 남아있는 경우 직계 자손
                // 들어오는 간선이 0이 되는 경우 큐에 추가
                if (n == 1) {
                    directChildren.get(parent).add(child);
                    q.offer(child);
                }
                indegree.put(child, n - 1);
            }
        }

        // 직계 자손 구하기
        for (String parent : directChildren.keySet()) {
            StringBuilder sb = new StringBuilder();
            PriorityQueue<String> children = directChildren.get(parent);
            sb.append(parent + " " + children.size() + " ");
            while (!children.isEmpty()) {
                sb.append(children.poll() + " ");
            }
            pq.offer(sb.toString());
        }

        while (!pq.isEmpty()) {
            ans.append(pq.poll() + "\n");
        }

        System.out.println(ans);
    }
}

 

결과