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

문제 링크: https://www.acmicpc.net/problem/21276

21276번: 계보 복원가 호석

1. 주의할 점

- String 형태의 배열을 어떻게 표현할 것인가?

- 위상정렬에 대해 알고 있어야 한다

 

2. 구현

- 사람들에 대한 정보를 People에 담는다

- People을 정렬한 뒤, HashMap에 넣는다

- 하나는 이름을 통해 Index를 알아내는 Map. 그리고 다른 하나는 Index를 통해 이름을 알아내는 revMap.

- 관계에 대한 정보는 Li[]에 담으며, 자신의 자손이 누구인지를 담고 있다.

- 관계에 대한 정보를 담을 때, Conn[]을 통해 자신의 조상(Root까지)의 수를 저장한다

- Conn[]의 값이 0이라면, 각 가문들의 시조이므로 Queue에 넣고 Ancestor 리스트에도 넣는다

- 시조의 수와 이름을 출력시킨 후, 위상정렬을 통해 관계도를 이어간다. 이때, 관계도는 새로운 List인 DirectChild에 저장한다

- DirectChild를 사용하여 요청에 대한 정보를 출력한다

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static int node;
    static List<String> people;
    static List<Integer> li[];
    static List<Integer> directChild[];
    static int conn[];
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    node = Integer.parseInt(br.readLine());
	    //초기화
	    people = new ArrayList<>();
	    li = new List[node];
	    directChild = new List[node];
	    for(int i=0;i<node;i++){
	        li[i] = new ArrayList<>();
	        directChild[i] = new ArrayList<>();
	    }
	    conn = new int[node];
	    HashMap<String, Integer> map = new HashMap<>();
	    HashMap<Integer, String> revMap = new HashMap<>();
	    
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    for(int i=0;i<node;i++){
	        String ss = st.nextToken();
	        people.add(ss);
	    }
	    Collections.sort(people);
	    int idx=0;
	    for(String ss : people){
	        map.put(ss,idx);
	        revMap.put(idx++,ss);
	    }
	    
	    int edge = Integer.parseInt(br.readLine());
	    for(int i=0;i<edge;i++){
	        str = br.readLine();
	        st = new StringTokenizer(str);
	        String child = st.nextToken();
	        String par = st.nextToken();
	        int cidx = map.get(child);
	        int pidx = map.get(par);
	        
	        conn[cidx]++;
	        li[pidx].add(cidx);
	    }
	    List<String> ancestor = new ArrayList<>();
	    Queue<String> q = new LinkedList<>();
	    for(int i=0;i<node;i++)
	        if(conn[i]==0){
	            ancestor.add(revMap.get(i));
	            q.offer(revMap.get(i));
	        }
	    System.out.println(ancestor.size());
	    for(String ss: ancestor)
	        System.out.print(ss+" ");
	   System.out.println();
	   while(!q.isEmpty()){
	       String ss = q.poll();
	       int sidx = map.get(ss);
	       for(int i=0;i<li[sidx].size();i++){
	           int next = li[sidx].get(i);
	           if(--conn[next]==0){
	                q.offer(revMap.get(next));
	                directChild[sidx].add(next);
	           }
	       }
	   }
	   
	   for(int i=0;i<node;i++){
	       String ss = people.get(i);
	       int sidx = map.get(ss);
	       System.out.print(ss+" "+directChild[sidx].size()+" ");
	       Collections.sort(directChild[sidx]);
	       for(int k=0;k<directChild[sidx].size();k++)
	            System.out.print(revMap.get(directChild[sidx].get(k))+" ");
	       System.out.println();
	   }
	}
}