inflearn

📘 10주완성 C++ 코딩테스트 강의를 수강한 후 정리한 글입니다. 깊이 우선 탐색 ( DFS, Depth First Search ) DFS는 그래프를 탐색할 때 쓰는 기법이다. 어떤 노드부터 시작해 인접한 노드들은 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않는다. 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘이다. DFS를 구현하는 방법 1️⃣ visited를 확인하고 함수 호출 2️⃣ 함수 호출 후 기저조건으로 함수 return ⬇ 수도코드 DFS( u , adj ) u.visited = true // 해당 노드 방문처리 for each v in adj[u] if v.visited == false //방문 여부 확인 DFS( v, adj )// 방문하지 않은 경우 방문( 재귀 ..