목록IT/Algorithm (1)

취미겸생업

[Algorithm] DFS, 백트래킹

DFSDFS(Depth-First Seach, 깊이 우선 탐색)란루트 노드에서 시작해, 다음 분기(Branch)로 넘어가기 전, 해당 분기를 완벽하게 탐색하는 방법이다. 노드 순회 시, 깊이를 우선으로 모든 노드를 방문하고자 할 경우 사용한다. 단순 검색 속도 자체는 BFS에 비해 느리다.특성전위 순회(Pre-Order) 방법 또한 DFS의 일종그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함 (검사하지 않을 경우 무한루프 발생)깊이 우선 순위로 모든 노드에 대한 완전 탐색DFS 과정요소의 역할Stack : 현재 탐색 상태(탐색한 경로와 되돌아갈 경로)를 기억하기 위한 자료구조Visited : 한 번 방문한 노드를 다시 방문하지 않기 위한, 모든 노드에 대한 방문 여부 체크리스트준비..
IT/Algorithm 2026. 7. 13. 15:32
이전 Prev 1 Next 다음