파이썬 깊이 우선 탐색1 [그래프] 깊이 우선 탐색 (DFS - Depth First Search) 알고리즘 학습 목표 깊이 우선 탐색 (Depth First Search) 개념, 예시, 의의 깊이 우선 탐색 개념 1) 정의 깊이 우선 탐색이란, 트리 구조나 그래프 데이터 구조를 탐색하는 알고리즘이다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색은 스택 구조를 사용한다. 2) 동작 예시 시작 노드에서부터 왼쪽이 우선 선택되었다고 가정하자. (1) 탐색 시작 노드를 스택에 삽입하고 '방문' 처리한다. (2) 방문하지 않은 인접 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. >> 방문할 수 있는 노드는 모두 방문 후, 없으면 돌아간다는 의미이다. (이 때 스택에서 추가되었던 값들이 하나씩 다시 제거된다.) (3) (2)번 과정을 반.. 2021. 2. 12. 이전 1 다음
