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

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

---

풀이

• 조상-자손 관계를 이용해서 위상 정렬
• 부모-자식 관계를 출력하는 건 전체 출력에서 자식의 이름이 한 번만 등장한다는 점을 이용할 수 있음. 가장 밑에서 부터 위로 올라가면서 자식들을 출력하는데 이미 나온 이름은 출력하지 않도록 하면 됨.
• 문자열 처리를 위해 HashMap 사용

---

코드

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

public class Main {
	public static class Person {
		public String name;
		public int indegree, outdegree;
		public ArrayList<Person> ancestors;
		public ArrayList<Person> descendants;
		public ArrayList<String> children;

		public Person(String name) {
			this.name = name;
			indegree = 0;
			outdegree = 0;
			ancestors = new ArrayList<>();
			descendants = new ArrayList<>();
			children = new ArrayList<>();
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		HashMap<String, Person> map = new HashMap<>();
		ArrayList<String> list = new ArrayList<>();
		ArrayList<String> progenitors = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			String name = st.nextToken();
			Person p = new Person(name);
			list.add(name);
			map.put(name, p);
		}

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

		while (M-- > 0) {
			st = new StringTokenizer(br.readLine());
			String descendant = st.nextToken();
			String ancestor = st.nextToken();
			map.get(descendant).ancestors.add(map.get(ancestor));
			map.get(descendant).outdegree++;
			map.get(ancestor).indegree++;
		}

		Stack<Person> stack = new Stack<>();
		HashSet<Person> usedChildren = new HashSet<>();
		int K = 0;

		for (String name : map.keySet()) {
			if (map.get(name).indegree == 0) {
				stack.add(map.get(name));
			}
			if (map.get(name).outdegree == 0) {
				progenitors.add(name);
				K++;
			}
		}

		while (!stack.empty()) {
			Person cur = stack.pop();

			for (Person p : cur.descendants) {
				if (!usedChildren.contains(p)) {
					usedChildren.add(p);
					cur.children.add(p.name);
				}
			}

			for (Person p : cur.ancestors) {
				p.descendants.add(cur);
				if (--p.indegree == 0) {
					stack.add(p);
				}
			}
		}

		StringBuilder sb = new StringBuilder().append(K).append('\n');
		Collections.sort(progenitors);
		Collections.sort(list);

		for (String name : progenitors) {
			sb.append(name).append(' ');
		}
		sb.append('\n');

		for (String name : list) {
			sb.append(name).append(' ').append(map.get(name).children.size());
			Collections.sort(map.get(name).children);
			for (String childName : map.get(name).children) {
				sb.append(' ').append(childName);
			}
			sb.append('\n');
		}

		System.out.println(sb);
		br.close();
	}
}

---

후기

내가 요령이 없는 건지 구현하는데 이것 저것 신경 쓰이는 게 많았던 문제,,
자손에서 조상으로 올라오기 보다는 역방향으로 내려오는 게 더 쉽다는 것 같다