[그래프 탐색] DFS

DFS란?

DFS(깊이 우선 탐색)는 그래프의 시작 노드에서 출발하여 탐색할 할 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘

DFS의 특징?

• 스택 자료구조를 사용하지만 보통은 스택 성질을 가지는 재귀 함수로 구현한다.
• 재귀함수를 이용하기 때문에 스택 오버플로(시간초과)에 유의해야한다. -> 다음 게시글에 설명할 BFS보다 느리다.
• 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열 필요

DFS의 동작과정

1. DFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화

• 인접 리스트 그래프로 표현하기
• 방문 배열 초기화하기
• 시작 노드 스택에 삽입하기

2. 스택에서 노드를 꺼낸 후 노드의 인접 노드를 다시 스택에 삽입

• pop을 수행해 스택에서 노드를 꺼낸다.
• 꺼낸 노드의 인접 노드들을 스택에 삽입
• 삽입한 노드들 방문 배열에 체크

3. 스택 자료구조에 값이 없을 때까지 반복

• 스택 자료구조에 값이 없어질 때까지 반복
• 이미 다녀간 노드는 재삽입하지 않는 것이 포인트