문제

트리의 부모 찾기

풀이

처음에는 DFS가 아닌 코드로 풀었었다

		StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            sb.append(arr[i].get(0)).append("\n");
            arr[i].remove(0);
        }
        System.out.println(sb);

하지만 이 경우에는 아직 부모가 정해지지 않은 경우 에는 에러 처리가 어렵다
주어진 예제에서는 1부터 그래프가 그려져 나오기 때문에 이 코드로도 전부 통과 한다
부모가 정해지지 않은 경우의 케이스 라는것은

노드의 개수가 3
2 3
1 2 의 경우이다

1 2가 나중에 나오는경우에는 2 3중 아직 어떤것이 루트인지 정해지지 않았는데 3의 루트가 1인것처럼 출력되게 된다
그렇기 때문에 이문제는 단순 arr를 출력할 수는 없었다. DFS로 앞전 노드가 부모라는 것을 확인 해야지 알수 있다.

boolean[] check = new boolean[n + 1];
        int[] answer = new int[n + 1];
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        while (!q.isEmpty()) {
            int x = q.poll();
            for (int a : arr[x]) {
                if (!check[a]) {
                    check[a] = true;
                    answer[a] = x;
                    q.add(a);
                }
            }
        }

그래서 다음과 같이 코드를 수정해준다
answer 의 배열은 인덱스의 부모를 담는 배열이 된다
그 외에는 전부 DFS 코드 이다

전체 코드

전체 코드