Dfs

출처 백준 개미 접근 완전탐색(DFS) 자식 방에서 부모(Root) 방향으로 DFS를 하면서 지상에 도달하는데 걸리는 시간을 확인합니다. 개미 방의 개수가 최대 10^5이므로, 최악의 경우인 방이 일렬로 나열된 경우를 고려해야 합니다.1 선형적인 DFS로는 시간복잡도가 초과할 것이라고 생각해서 BinarySearch로 최적화를 했는데, 선형으로 조상들을 탐색해도 시간초과가 되지 않는 것으로 보아 DFS 만으로도 풀 수 있을 것 같습니다. TREE + BinarySearch 문제를 다시 읽어보면 자신 부모들의 집합, 즉, 조상들을 하나씩 타고 올라가면서 갈 수 있는 최대 조상의 번호를 반환해야 함을 알 수 있습니다. ...