깊이우선탐색 썸네일형 리스트형 알고리즘 3. DFS(깊이 우선 탐색) 트리의 순회, 점화식 구현 등 DFS(재귀 구조)에 특화된 문제인 경우 깊이 우선 탐색(DFS) 사용1. 깊이 우선 탐색(DFS)이란?① 그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법이다.② [완전 탐색]을 수행하기 위해 사용할 수 있는 가장 간단한 방법 중 하나다③ 스택(stack) 자료구조를 사용한다. 2. 깊이 우선 탐색(DFS) 기본 동작 방식1) 시작 노드를 큐에 넣고 [방문 처리]한다.2) 스택에 마지막으로 들어 온 노드에 방문하지 않은 인접 노드가 있는지 확인한다. 있다면, 방문하지 않은 인접 노드를 스택에 삽입하고 [방문 처리]한다. 없다면, 현재 노드(스택에 마지막으로 들어 온 노드)를 스택에서 추출한다.3) 2번 과정을 더 이상 반복할 수 없을 때까지 반복한다.. 더보기 이전 1 다음
