[알고리즘] DFS 깊이 우선 탐색

 
✏️해당 포스트는 인프런 알고리즘 코딩테스트 핵심이론 강의를 토대로 정리한 내용입니다.
 
 
탐색엔 깊이 우선 탐색, 너비 우선 탐색, 이진 탐색으로 크게 나누어진다. 
이 중에서 DFS는 모든 코딩 테스트에서 다루는 알고리즘 영역 중에 가장 많이 사용한다고 한다.
예전 자료구조랑 고급자료구조 시간에 열심히 배웠던 게 생각이 나는데 (그때도 시험 문제에 단골로 출제되었다)
오늘은 한번 제대로 정리하고 넘어가고자 한다.
 

---

 

⭐깊이 우선 탐색 (DFS) 이란? 

 
깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나다. (완전 탐색은 그래프에 있는 모든 노드를 탐색하는 것)
그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색 후 다른 쪽 분기로 이동하여 다시
탐색을 수행하는 알고리즘이다. 
 
보통 시간 복잡도는 O(V+E) 이때 V 는 노드 수, E는 에지 개수다. 
 
 
수도 코드는 다음과 같다. 

depthFistSearch(v) 

		v를 방문되었다고 표시; 
        for all u ∈(v에 인접한 정점) do 
        	if (u가 아직 방문되지 않았으면)
            	then depthFirsthSearch(u)

 

 

 

그림 출처 :https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html#google_vignette

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

 
 
갈 수 있는 한 최대한 들어갔다가 막히면 이전 상태로 되돌아간다는 점에서 재귀호출, 스택 구조(FILO, 후입선)를 통해 구현한다.
재귀 함수는 스택 오버플로우에 유의해야한다.  (무서운 스택 오버 플로우...)
 
A라는 함수에서 또 A를 부르고 이걸 계속 반복하게 되면 메모리가 누적되는데 이때 스택 오버 플로우가 발생한다. 따라서 DFS를 구현할 때는 스택 오버 플로우를 고려하여 로직을 짜야한다. 
 
 
 
 💠스택 오버 플로우란? 

 

• 스택 오버플로우란, 프로그램 실행 중 스택 메모리 공간이 초과될 때 발생하는 오류이다.
• 주로 재귀 함수를 사용할 때, 함수 호출이 너무 깊어져 스택에 너무 많은 함수 호출 정보가 쌓일 때 발생한다.

 

 
 
깊이 우선 탐색을 응용하여 풀 수 있는 문제 (그래프 완전 탐색 ) 

• 단절점 찾기
• 단절선 찾기
• 사이클 찾기
• 위상 정렬 

 

---

 

 

⭐깊이 우선 탐색 (DFS) 핵심 이론 

 
 
DFS는 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하다.
그래프는 보통 인접 리스트로 표현한다. 또한 DFS의 탐색 방식은 후입선출이기 때문에 스택을 사용해야한다. 
 
보통 DFS 구현을 할 때는 스택보다는 스택 성질을 갖는 재귀함수로 많이 구현한다고 한다. 
 
 
 
1) DFS 시작할 때 노드를 정한 후 사용할 자료 구조 초기화 하기 (이때 자료구조는 인접리스트) 
 
 

 
 
 

• 그래프를 인접 리스트로 변환하고 시작점을 정한다. 
• 방문 배열을 생성하고 시작점을 T로 표시한다. (아직 방문하지 않은 정점은 F ）
• 스택에 시작점을 push하여 DFS를 시작한다. 
• 스택에서 노드를 꺼내 인접한 방문하지 않은 노드를 다시 push하며 탐색을 반복한다.

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

 
 

• 스택에서 노드 1을 꺼내 탐색 순서에 기록한다. (pop 수행) 
• 노드 1의 인접 노드 2, 3을 확인한다. (인접 리스트의 인접 노드를 스택에 삽입) 
• 방문하지 않은 노드 3, 2를 스택에 역순으로 삽입한다.
• 노드 2와 3을 방문 배열에 체크(true)한다

 
 
3) 스택 자료 구조에 값이 없을 때까지 다음 과정 반복하기 
 
 
이때 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는다! 
 

 

• 스택에서 노드를 꺼내며 탐색 순서를 1 → 3 → 4 → 6으로 기록한다.
• 각 노드의 인접 노드를 확인하고, 아직 방문하지 않은 노드만 스택에 삽입한다.
• 이미 방문한 노드(노드 6)는 스택에 넣지 않으며, 인접 노드가 없으면 삽입 없이 다음으로 진행한다.
• 최종적으로 탐색 순서는 1 → 3 → 4 → 6 → 2 → 5로 완성된다.

 
 
 
💡스택에 노드를 삽입할 때 배열을 체크하고 스택에서 노드를 뺄 때 탐색 순서에 기록하여 인접 노드를 방문 배열과 대조하여 살펴볼 것 
 
 
손으로 한번 그래프를 그려본 뒤 과정을 수행해보면 좀 더 쉽게 이해가 되는 것 같다.  

 
 

---

 
이건 자료구조 들었을 때 배웠던 코드 정리해둔 것. 다시보고 코드를 복습해보았다. 
 
 
DFS 구현 (인접행렬) 

//탐색 기능이 추가된 인접 행렬 기반 그래프 클래스
class SrchAMGraph : public AdjMatGraph{
	bool visited[MAX_VTXS]; // 정점의 방문 정보 
    void resetVisited() {  // 모든 정점을방문하지 않았다고 설정 즉 f 로 설정해둔다  
    	for (int i=0; i< size; i++ )
        	visited[i] = false; 
    }
    bool isLinked(int u, int v) { 
    	return getEdge(u,v)!=0; // 0이 아니라면 true, 즉 연결되어있다는 뜻이다 반대로 0이라면 연결이 안되어있다는 뜻! 
     }
    
    //깊이 우선 탐색 함수 
    void DFS(int v) {
    	visited[v] = true; // 현재 정점을 방문함 
        printf("%c" , getVertex(v)); // 정점의 ㅇ이름 출력하기 
     
    	for(int w=0; w<size ; w++)
        	if( isLinked(v,w) && visited[w] ==false) 서로 연결이 되어있고 방문을 안했을 때
           		DFS(w); // 순환호출로 방문한다 
       }
   };