문제 이해

N명의 사람이 주어지고, (X Y) 형식으로 입력이 M개 주어진다.
(X Y)는 X의 조상 중에 Y가 있다는 것을 의미한다.

이렇게 입력이 주어졌을 경우 이름의 사전순대로 사람 이름, 자식 수, 자식들의 이름(사전순)을 순차적으로 출력하는 문제이다

---

문제 풀이

결국은 조상 Node를 줄테니 Tree를 형성하라는 문제이다.

Tree의 가장 큰 특징은 "부모 Node가 한 개"라는 조건이다.
따라서 위상 정렬을 활용해보기로 했다.
indegree 배열을 활용해서 자식 노드 -> 조상 노드 방향으로 indegree가 들어오는 방법을 생각해보았다.

내가 생각한 로직은 아래 순서와 같다.

1. 이름을 입력받고 사전 순서대로 정렬한다

   • 나중에 출력을 이름 순서로 해야하므로 미리 정렬해 놓는게 편함

2. 자식-부모 관계를 HashMap 형태로 저장한다.

   • 나는 Key를 조상, Value를 자식(혹은 손자) Node로 지정했다.

3. "조상 노드"에 들어오는 화살표로 생각했기 때문에 indegree[자식 노드] 값을 1 증가시켰다.

4. Queue에 indegree = 0인 값들을 모두 넣어준 이후, 해당 Index와 연결된 자식 노드들의 indegree를 1씩 감소시키며 계속해서 indegree = 0인 Node들을 Queue에 넣어주는 형식으로 위상정렬을 실시하였다

   • 연결된 자식 노드들 중 indegree = 0이 되는 자식 노드들은 트리 위쪽으로는 오로지 조상 노드와만 연결되어 있다는 의미이므로, 부모 노드가 된다.
   • 이 부분은 코드 상에서 자세히 설명

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	
	static int N, M;
	static String[] names;
	static int[] indegree;
	static HashMap<String, ArrayList<String>> parent_son, answer;
	static HashMap<String, Integer> name_num;
	
	static void sort() {
    // 위상 정렬 코드
		Queue<Integer> queue = new LinkedList<>();
		for(int i =0;i<N;i++) {
        // 조상 노드가 없는 Node들을 Queue에 저장
        // 조상 노드가 없다 = 한 가문의 시조 Node이다.
			if(indegree[i]==0) {
				queue.add(i);
				sb.append(names[i]+" ");
			}
		}
        
		sb.insert(0, queue.size()+"\n");
		sb.append("\n");
        // 가문 시조 노드 개수 = 가문의 개수
        
		while(!queue.isEmpty()) {
			int tmp = queue.poll();
			
			for(String s:parent_son.get(names[tmp])) {
				indegree[name_num.get(s)]--;
                // 위상 정렬에 의해 Node들을 하나씩 없앨 것이다.
                // 여기서 "조상 노드"가 없어지도록 알고리즘을 구현했다.
                // 즉, 조상 노드와 연결된 모든 자식 노드들의 indegree는 1씩
                // 감소한다
                
                // 만약, indegree가 1 감소한 자식 노드의 조상 Node 개수가 
                // 0이라고 가정하자
                // 그런 자식 Node들은 결국 조상 Node가 현재 확인하고 있는
                // Node밖에 없다는 의미이므로 현재 Node의 자식 Node에 추가
                // 시켜주고, Queue에 추가시켜 다음에 제거할 Node로 지정한다
				
				if(indegree[name_num.get(s)]==0) {
					queue.add(name_num.get(s));
					answer.get(names[tmp]).add(s);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		
		FastReader sc = new FastReader();

		N = sc.nextInt();
		names = sc.nextLine().split(" ");
		Arrays.sort(names);
		
		name_num = new HashMap<>();
        // 각 이름에 대응되는 숫자를 위한 HashMap
        // indegree를 활용할 때 Index는 숫자여야만 하므로 활용
		parent_son = new HashMap<>();
        // 조상-자식 노드 관계를 표현할 HashMap
        // Key : 조상, Value : 자식(후손) 노드들
		answer = new HashMap<>();
		indegree = new int[N];
        // indegree[k] : 조상 노드들의 개수
		
		for(int i =0;i<N;i++) {
			parent_son.put(names[i], new ArrayList<>());
			answer.put(names[i], new ArrayList<>());
			name_num.put(names[i],i);
		}
		
		M = sc.nextInt();
		
		for(int i =0;i<M;i++) {
			String[] tmp = sc.nextLine().split(" ");
			
			parent_son.get(tmp[1]).add(tmp[0]);
			indegree[name_num.get(tmp[0])]++;
		}
		
		sort();
		
		for(int i =0;i<N;i++) {
			sb.append(names[i]+" "+answer.get(names[i]).size()+" ");
			Collections.sort(answer.get(names[i]));
			for(String s:answer.get(names[i])) {
				sb.append(s+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 런타임 에러 : N과 M을 헷갈려서 for문에 활용해 에러 발생

• 틀렸습니다 : 출력값으로 처음에 가문 시조들 개수를 출력했어야 했는데, 이 부분을 구현하지 않아서 틀림