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

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

 

해당 문제에서는 제일 먼저 가문의 개수와 가문의 시조를 구해야 합니다. 가문의 개수를 구하는 방법은 자신을 바라보는 정점이 없는 정점 즉 루트가 몇 개인지 확인하고 그 값을 출력을 하면 됩니다. 그래서 가문의 시조를 관리하는 리스트를 만들어 이를 해결하여습니다.

 

위 말을 조금 더 쉽게 생각하면 부모가 있어야 자식이 있기 때문에 부모 -> 자식 관계로 생각을 하면 합니다. 즉 최상위 조상은 누구도 자신을 바라보지 않습니다. 그리고 자식들을 출력을 해야하는데 이 또한 리스트를 활용하여 각 정점마다 자식을 추가 해주었습니다.

for(int i = 0 ; i < strArr.length ; i++){
	Queue<Integer> q = new LinkedList<>();
	int idx = map2.get(strArr[i]);
	q.offer(idx);
	while(!q.isEmpty()){
		Integer poll = q.poll();
		for(int value : lst[poll]){
			if(--arr[value] == 0){
				q.offer(value);
				c[poll].add(map1.get(value));
			}
		}
	}
}

arr[value]이 0이 되면 지금의 poll의 자식이 됩니다. 이를 통해 리스트를 채우고 출력을 해주면 해결할 수 있습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Backjoon_21276_계보_복원가_호석 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        HashMap<Integer, String> map1 = new HashMap<>();
        HashMap<String, Integer> map2 = new HashMap<>();
        ArrayList<Integer>[] lst = new ArrayList[N];
        ArrayList<String>[] c = new ArrayList[N];
        int[] arr = new int[N];

        String[] split = br.readLine().split("\\s");
        Arrays.sort(split);

        for(int i = 0 ; i < split.length ; i++){
            map1.put(i, split[i]);
            map2.put(split[i], i);
            lst[i] = new ArrayList<>();
            c[i] = new ArrayList<>();
        }

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

        for(int i = 0 ; i < M ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String V1 = st.nextToken();
            String V2 = st.nextToken();

            int idx1 = map2.get(V1);
            int idx2 = map2.get(V2);

            lst[idx2].add(idx1);
            arr[idx1]++;
        }


        ArrayList<String> p = new ArrayList<>();
        for(int i = 0 ; i < N ; i++){
            if(arr[i] == 0){
                String str = map1.get(i);
                p.add(str);
            }
        }
        String[] strArr = p.stream().toArray(String[]::new);
        Arrays.sort(strArr);

        sb.append(strArr.length).append("\n");
        for(String value : strArr){
            sb.append(value + " ");
        }
        sb.append("\n");

        for(int i = 0 ; i < strArr.length ; i++){
            Queue<Integer> q = new LinkedList<>();
            int idx = map2.get(strArr[i]);
            q.offer(idx);
            while(!q.isEmpty()){
                Integer poll = q.poll();
                for(int value : lst[poll]){
                    if(--arr[value] == 0){
                        q.offer(value);
                        c[poll].add(map1.get(value));
                    }
                }
            }
        }

        for(int i = 1; i < c.length; i++){
            sb.append(map1.get(i) + " ").append(c[i].size() + " ");
            Collections.sort(c[i]);
            for(String s : c[i]){
                sb.append(s + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}