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

axiom·2021년 9월 5일
0

계보 복원가 호석

1. 힌트

1) 주민들은 모든 조상을 완벽하게 기억하고 있습니다. 따라서 주어진 정보로 만들 수 있는 트리는 하나 뿐입니다.

2) XYX \to Y를 반대로 생각해서 YY에서 XX로 가는 간선으로 생각해봅시다. 이렇게 하면 indegree가 00인 정점이 각 가문의 시조를 알 수 있습니다.

3) 위상 정렬을 이용해서 Indegree가 00인 정점을 갱신해가면서 그래프를 구성하면 트리의 루트부터 아래로 쭉 정보를 알 수 있습니다.

2. 접근

1) Map

오름차순으로 출력해야하니까 주어진 사람들의 이름들을 정렬합시다. 그러면 ((번호,, 이름))꼴로 저장할 수 있습니다. 여기에 ((이름,, 번호))꼴도 처리할 수 있도록 Map을 선언하면 더 편리합니다.

3. 구현

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		String[] S = new String[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) S[i] = st.nextToken();
		Arrays.sort(S);
		// 이름이 주어지면 사전순으로 정렬했을 때 몇 번째인지 반환하는 map
		Map<String, Integer> m = new HashMap<>();
		for (int i = 0; i < N; i++) m.put(S[i], i);
		// 위상정렬을 위해 어떤 정점에 들어오는 간선의 개수 저장
		// X -> Y : X의 조상 중 Y가 있다
		// 가장 위에 있는 조상부터 고를 수 있도록 간선의 방향은 Y -> X가 됨
		int[] indegree = new int[N];
		boolean[][] adj = new boolean[N][N];
		int M = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int u = m.get(st.nextToken());
			int v = m.get(st.nextToken());
			adj[v][u] = true;
			indegree[u]++;
		}
		// 들어오는 간선이 없는 정점은 시조
		int cnt = 0;
		for (int i = 0; i < N; i++)
			if (indegree[i] == 0) cnt++;
		bw.append(cnt).append("\n");
		Queue<Integer> q = new LinkedList<>();
		// 사전순으로 출력해야하므로 정렬된 배열 S의 순서에 맞게 큐에 삽입
		for (int i = 0; i < N; i++) if (indegree[i] == 0) {
			bw.append(S[i]).append(" ");
			q.offer(i);
		}
		bw.append("\n");
		// i번째 정점의 자식들을 사전순으로 정렬하기 위해서 우선순위 큐 사용
		ArrayList<PriorityQueue<Integer>> T = new ArrayList<>(N);
		for (int i = 0; i <= N; i++) T.add(new PriorityQueue<>());
		for (int i = 0; i < N; i++) {
			// indegree가 0인 가장 조상인 정점을 뽑는다
			int here = q.poll();
			for (int there = 0; there < N; there++) if (adj[here][there]) {
				indegree[there]--;
				// 새롭게 indgree가 0인 정점이 있으면 큐에 삽입
				// 마찬가지로 S는 정렬되어 있으므로 큐에는 오름차순으로 들어감
				if (indegree[there] == 0) {
					q.offer(there);
					T.get(here).offer(there);
				}
			}
		}
		for (int i = 0; i < N; i++) {
			bw.append(S[i]).append(" ");
			bw.append(T.get(i).size()).append(" ");
			PriorityQueue<Integer> pq = T.get(i);
			while (!pq.isEmpty()) bw.append(S[pq.poll()]).append(" ");
			bw.append("\n");
		}
		System.out.print(bw);
	}

}
profile
반갑습니다, 소통해요

0개의 댓글