깊이 우선 탐색(DFS)

※이 글은 나동빈님의 유튜브를 보고 복습용으로 포스팅됩니다※

https://blog.naver.com/ndb796/221230945092

16. 깊이 우선 탐색(DFS)

깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘입니다. 가까운게 우선이었던 너비 우선 탐색과는 다른 느낌이죠. 이 깊이라는 게 좀 애매하다고 느끼실 분도 계실 거 같습니다. 그냥 가장 아래까지 내려갔다 돌아오는 알고리즘이라고 생각하시면 될거 같아요. 

 

BFS와 동일하게 DFS는 맹목적으로 각 노드를 탐색할 때 주로 이용 됩니다. 여기서는 Stack 이 사용이 되어. 사실 컴퓨터 구조자체가 항상 스택의 원리로 돌아가기 때문에 재귀를 써서 구현을 해도 괜찮습니다. 스택을 잘 모르신다면 아래 포스팅을 한 번 봐주세요ㅎㅎ

https://com24everyday.tistory.com/108

알고리즘 스택, 큐

 

우리가 탐색할 그래프와 스택입니다. 반대쪽이 막혀있으니깐 스택인 걸 알 수가 있죠! 노드를 방문하면 '방문처리'를 빨간색으로 해주겠습니다. 그럼 시작 노드 1을 방문하고 스택에 삽입해보겠습니다.

DFS는 아래의 알고리즘에 따라서 동작하게 됩니다. 

1. 스택의 최상단 노드를 확인

2. 최상단 노드에게 방문하지 않은 인접 노드가 존재하면 그 노드를 스택에 넣고 방문처리. 인접 노드가 없으면 스택에서 뺍니다. 

 

이걸 반복 수행해주시면 됩니다. 

 

1이 반복하지 않은 인접 노드는 2,3 입니다. 이 중 2를 스택에 넣습니다. 그리고 2의 인접 노드 중 방문하지 않은 3을 스택에 넣습니다. 아래는 그 결과입니다. 

이제 3의 노드들 중 방문하지 않은 6을 넣습니다.

6의 인접 노드 중 방문하지 않은 7을 넣습니다.

7의 인접 노드 중 방문하지 않은 노드가 없습니다. 그러면 최상단 노드인 7을 스택에서 빼줍니다. 

최상단 노드인 6도 다음 최상단 노드인 3도 방문하지 않은 인접 노드가 없으므로 스택에서 빼줍니다.

이제 최상단 노드인 2입니다. 2에겐 아직 방문하지 않은 인접노드 4,5가 존재합니다. 이 중 4를 스택에 넣겠습니다.

최상단 노드 4에 방문하지 않은 인접노드는 5입니다. 이 노드를 방문하고 스택에 넣어주겠습니다.

최상단 노드 5에겐 방문하지 않은 노드가 없습니다. 스택에서 꺼내줍니다.

최상단 노드 4에겐 방문하지 않은 노드가 없습니다. 스택에서 꺼내줍니다.

이렇게 쭉 꺼내주면 7, 6, 3, 5, 4, 2, 1 이 됩니다. 방문 경로는 1 2 3 6 7 4 5 입니다. 

 

이제 DFS 깊이 우선 탐색 과정을 파악하셨을거 같습니다. C++ 로 구현을 해보겠습니다.

#include <iostream>
#include <vector>

using namespace std;

int number = 7;//노드 수
int c[8];//방문처리를 위한 배열
vector<int> a[8];//7개의 노드가 각각 인접한 노드를 가질 수 있게

void dfs(int x) {
    if (c[x]) return;//방문한 노드이면 바로 리턴
    //방문을 안 한 노드
    c[x] = true;//방문 처리 
    cout << x << ' ';
    for (int i = 0; i < a[x].size();i++) {
        int y = a[x][i];//인접한 노드
        dfs(y);
    }
}

int main()
{
	//1과 2를 연결 
	a[1].push_back(2);
	a[2].push_back(1);

	//1과 3을 연결 
	a[1].push_back(3);
	a[3].push_back(1);

	//2과 3을 연결 
	a[2].push_back(3);
	a[3].push_back(2);

	//2와 4를 연결 
	a[2].push_back(4);
	a[4].push_back(2);

	//2과 5을 연결 
	a[2].push_back(5);
	a[5].push_back(2);

	//4과 5를 연결 
	a[4].push_back(5);
	a[5].push_back(4);

	//3과 6을 연결 
	a[3].push_back(6);
	a[6].push_back(3);

	//3과 7을 연결 
	a[3].push_back(7);
	a[7].push_back(3);

	//6과 7을 연결 
	a[6].push_back(7);
	a[7].push_back(6);

	dfs(1);
}

방문경로

오늘은 깊이 우선 탐색(DFS)에 대해 알아봤습니다 . BFS와 마찬가지로 다른 알고리즘에 적용하는 게 더 중요하기 때문에 동작 원리를 잘 알아두어야합니다. 감사합니다.

https://com24everyday.tistory.com/109?category=1123820

너비 우선 탐색(BFS)