알고리즘,PS/백준
2021. 6. 15.
[BOJ] 백준 [1068] 트리 JAVA
문제 풀이 생각보다 간단한 문제이다 . 끊어질 노드를 C 라고 하자. 그래프를 ArrayList 배열로 만든 뒤 끊어질 노드'C'의 위치까지 처음부터 다 받아서 그래프를 단방향으로 연결할 때 C가 나오면 연결을 안 해주면 끝. root 부터 DFS 돌리면서 ArryList의 size가 0이면 leaf 노드이다. 입력 노드'e' 를 받을때 3가지의 경우로 나눌 수 있는데 1. e 가 root 일때 => e == -1 2. e 가 끊어질 노드 'C' 이거나 연결하려는 노드의 부모노드가 'C'일때 => ( e==C || i ==C ) 3. 그외 경우엔 단방향 연결 단방향으로 연결이 완성된 그래프를 root 부터 DFS 재귀호출을 이용하여 자식이 없는 노드를 카운트하면 끝. 이때 , 끊어질 노드 'C'가 roo..