공부한 내용 기록하기 공부한 내용 기록하기

1. 깊이 우선 탐색이란?깊이 우선 탐색(DFS, Depth-First Search)은 그래프나 트리를 탐색하는 대표적인 방법 중 하나로, 특정 경로를 따라 최대한 깊이 내려간 후 더 이상 진행할 수 없으면 되돌아가면서 미탐색 노드를 방문하는 방식으로 동작한다.DFS는 스택(LIFO: 후입선출) 구조를 활용하며, 재귀 호출이나 명시적인 스택 자료구조를 사용해 구현할 수 있다.2. 깊이 우선 탐색의 동작 원리DFS는 다음과 같은 과정으로 수행된다:시작 노드를 방문하고 방문 표시를 한다.현재 노드에서 인접한 노드를 차례대로 탐색한다.아직 방문하지 않은 노드가 있다면 해당 노드로 이동하고 위 과정을 반복한다.더 이상 방문할 노드가 없으면 이전 노드로 되돌아간다.2.1 깊이 우선 탐색 과정 예제다음과 같은 그래..