DFS 깊이우선 탐색방식에 대해서 알아보자 part1(스테픈 2km완료)
1 comment
오늘은 깊이 우선탐색 방식인 dfs 알고리즘에 대해서 알아보자
저번 포스팅 완전탐색에 관해서 작성할때 언급했던 DFS
DFS(Depth-First-Search)는 깊이 우선 탐색이라고 하며 그래프에서 깊은 부분을 우선으로 탐색하는 알고리즘이다.
우리가 드라마나 만화책을 볼때
1권부터 완결까지 쭉 보는 방식이 DFS라고 생각하면 편하고
만화책방에 다양한 만화책을 1권식 가져다가 읽어보고 다읽었으면 다시 2권을 전부 가져와서
읽어보는 방식을
BFS라고 한다.
일단 오늘은 DFS에 대해서 정리한다.
- 자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.
- 이 알고리즘은 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다.
- 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
사진출처 : https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
노드(시작 노드)를 방문한다.
방문한 노드는 방문했다고 표시한다.
인접하는 노드를 차례로 순회한다
이미 방문한 노드라면 패스한다.
방문한적 없는 노드라면 해당 노드를 시작노드로 변경하고
위 과정을 반복한다.
시작 노드의 인접한 노드를 모두 방문했다면 위 과정을 종료한다.
깊이 우선 탐색은 두가지 방식으로 구현이 가능한데
얼마전 공부했던 재귀함수를 통한 구현방법과
반복문과 스택을 활용하여 구현하는 방식
재귀함수를 사용하는 방식의 경우 깊이가 깊어질수록 스택이 너무 과하게 쌓여서 스택오버플로우의 위험이 있다.
아마도 시간제한이 있는 코딩테스트에서는 재귀로 구현했을때 이러한 문제점이 발생할 수 있을것 같다.
만드는 방식은 두가지 다 해보자
재귀 방식의 DFS
인접하는 노드에 대한 정보를 변수에 나타낸다면
[[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]] 이렇게 될것이다.
숫자 1은 0과 5가 인접한 노드이고, 숫자 5는 1하고 2가 인접한 노드.. 이런식으로 인접한 노드 정보를 받고 방문한 이력을 남겨 재방문하지 않도록 하여 함수를 구성한다면 아마 이런식으로 구현이 가능할것이다.
재방문을 방지하기 위해
visited 를 Set이라는 데이터 구조를 사용해서 중복값을 제거했고
반복문 속에서 재귀 호출을 통해 깊이 우선탐색을 진행했다.
콘솔로그로 찍힌 값을 보면 정상적으로 전부 방문을 했다는걸 알 수 있다.
이러한 재귀함수로 처리한 내용은 반복문으로도 처리가 가능한데
다음포스팅에서 이어서 작성해야겠다.
스테픈 2km완료 
)
Comments