목록Depth First Search (1)

포시코딩

DFS(Depth First Search) - 깊이 우선 탐색

DFS란? 자료의 검색, 트리나 그래프를 탐색하는 방법으로 사용되며 한 노드를 시작으로 인접한 다른 노드를 통해 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. DFS의 특징 DFS는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구한다. 따라서 공간을 적게쓰지만 최단 경로를 탐색하기가 쉽지 않다. DFS 구현 방법 1. 재귀함수 DFS는 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조이다. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문 또 그 노드를 방문해서 깊이 우선으로 인접한 노드 방문 만약 끝에 도달했다면 리턴 -> 반복.. 반복하다가 갈 수 없게 되면 탈출 -> 재귀 함수를 쓰면 되겠구나 코드로 직접 살펴보자 graph = {..
자료구조알고리즘/이론 2022. 11. 29. 17:19
이전 Prev 1 Next 다음