처음에는 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 코드 이다