백준 21276 (계보 복원가 호석) - java

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

21276번: 계보 복원가 호석

 

문제 

석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다.

그러던 어느 날, 유구한 역사를 지닌 석호촌의 도서관에 화재가 나서 계보들이 모두 불타고 말았다. 그래도 계보는 있어야 하지 않겠느냐는 마을 어르신인 대일 촌장님의 의견에 따라 석호촌 사람들은 계보 복원가 호석에게 의뢰를 맡기기로 했다.

적어도 현재를 함께 살아가는 N 명의 계보는 복원하고 싶은 호석이는 조사를 통해서 각자가 기억하는 조상들의 이름들을 구해냈다. 다행히도 석호촌의 맑은 정기 덕분에 기억력이 굉장히 좋은 주민들은 모든 조상을 완벽하게 기억하고 있다. 또한, 각 가문은 한 명의 시조를 root로 하는 트리 형태를 띈다는 것도 알아냈다. 이 때 "조상"이란, "자신의 부모"와 "부모의 조상"을 모두 합친 것을 의미한다.

이를 기반으로 몇 개의 가문이 존재했는 지, 각 가문에 대한 정보를 출력하는 프로그램을 작성해서 호석이를 도와주자!

7
daeil sangdo yuri hoseok minji doha haeun
7
hoseok sangdo
yuri minji
hoseok daeil
daeil sangdo
haeun doha
doha minji
haeun minji

 

유형 : 위상정렬

 

접근 방식

• 입력의 형식을 보면 직속 부모와 자식만 주어지지 않는다.
  • 하지만 사실 이런 입력 형식은 그닥 중요하지 않는다.
• 결국 위상정렬로 해당 문제를 접근하게 될 경우 들어오는 간선의 개수를 한 개씩 줄여나갈 것이다.
  • 만약 줄고 줄어서 0이 되는 순간 0이 되게 만든 노드가 직속 부모일 것이다.
• 문제 자체가 어렵지는 않다. 하지만 출력 형식을 일치시키는 것이 조금 까다롭다.
  • 클래스를 하나 만들어서 해당 클래스의 배열을 정렬하는 방식을 사용했다.
• 입력이 문자열로 주어지기 때문에 map을 사용해서 int값으로 접근하는 것도 중요하다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static int[] board;
    static HashMap<Integer,String> pn = new HashMap<>();
    static HashMap<String,Integer> pn2 = new HashMap<>();
    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        board = new int[n+1];

        graph = new ArrayList[n+1];

        st = new StringTokenizer(bf.readLine(), " ");

        for(int i=1;i<=n;i++){
            String cur = st.nextToken();
            graph[i] = new ArrayList<>();
            pn.put(i,cur);
            pn2.put(cur,i);
        }

        st = new StringTokenizer(bf.readLine(), " ");
        m = Integer.parseInt(st.nextToken());

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(bf.readLine(), " ");
            String f = st.nextToken();
            String s = st.nextToken();

            int fn = pn2.get(f);
            int sn = pn2.get(s);

            graph[sn].add(fn); // 그래프
            board[fn] += 1; // 위상정렬 표 갱신
        }

        StringBuilder sb = new StringBuilder();
        int num = 0;

        PriorityQueue<String> pq = new PriorityQueue<>(
                (x,y) -> x.compareTo(y)
        );

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

        for(int i=1;i<=n;i++){
            if(board[i] == 0){
                num += 1; // 최상위 노드의 개수
                pq.add(pn.get(i)); // 문자열 오름차순
                q.add(i); // 위상정렬 시작 노드
            }
        }

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


        Node[] result = search(q);

        for(int i=0;i<n;i++){

            sb.append(pn.get(result[i].root)+" "+result[i].count+" ");

            StringBuilder ch = new StringBuilder();

            while(!result[i].child.isEmpty()){
                ch.append(result[i].child.poll()+" ");
            }

            sb.append(ch);
            sb.append("\n");
        }


        System.out.print(sb);
        bf.close();
    }

    static Node[] search(Queue<Integer> q){
        int[] childNum = new int[n+1];
        int[] root = new int[n+1];
        ArrayList<Integer>[] childList = new ArrayList[n+1];

        for(int i=0;i<=n;i++){
            childList[i] = new ArrayList<>();
        }

        while(!q.isEmpty()){
            int cur = q.poll();

            for(int next : graph[cur]){
                board[next] -= 1; // 들어오는 간선을 한 개씩 제거한다

                if(board[next] == 0){
                    root[next] = cur; // 들어오는 간선이 0이 되었다는 것은 cur이 next의 바로 직속 부모라는 것이다
                    childNum[cur] += 1; // cur의 자식의 개수 1개 증가
                    childList[cur].add(next); // 자식의 정보 추가
                    q.add(next);
                }
            }
        }

        Node[] arr = new Node[n];

        for(int i=1;i<=n;i++){
            int num = i-1;

            arr[num] = new Node(i,childNum[i]);
            for(int next : childList[i]){
                arr[num].child.add(pn.get(next));
            }
        }

        Arrays.sort(arr,(x,y) -> {
            return pn.get(x.root).compareTo(pn.get(y.root));
        }); // 정렬 (부모의 이름이 오름차순)

        return arr;
    }
}
class Node{
    int root;
    int count;
    PriorityQueue<String> child;

    Node(int root,int count){
        this.root = root; // 부모 노드
        this.count = count; // 자식의 개수
        this.child = new PriorityQueue<>(
                (x,y) -> x.compareTo(y) // 자식의 정보 (문자열 오름차순)
        );
    }
}