잡다한 IT 지식

주어진 트리 노드에서 노드의 값을 val이라고 정의했을 때, low

참고한 영상 DFS 위키백과 깊이 우선 탐색(Depth-First Search) 최대한 깊은 단계까지 우선 검색하는 방법. 구현방법으론 스택과 재귀식 구현이 있음. 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다. 영상 보면서 직접 ..