[그래프] DFS에 대하여...

이전 게시물인 BFS와 마찬가지로 모든 노드에 방문하는 탐색 방법 입니다.

DFS도 BFS와 마찬가지로 기본 틀을 알아두시면 코드를 쉽게 작성하실 수 있습니다.

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

DFS는 말 그대로 탐색할 수 있는 끝까지 갔다가 목적지가 아니면 다시 되돌아와서 탐색하는 방법입니다.

가장 쉬운 예로 미로탐색을 들 수 있습니다.(나중에 관련 문제를 풀고 링크를 첨부해드리겠습니다!)

또, DFS는 스택, 반복문, 재귀 같은 방법으로 구현할 수 있습니다.

하지만 여기서는, 재귀에 대한 설명만 하도록 하겠습니다.(가장 많이 쓰이기 때문)

1. 루트 노드를 방문합니다.

2. 우선순위가 가장 높은 자식노드를 방문합니다.

3. 방문한 노드의 자식노드가 있다면 계속 내려갑니다.

4. 방문할 노드가 없다면 이전 노드로 방문합니다.

5. 2~4를 반복합니다.

아래 링크는 BFS에 대한 글이지만 BFS와 DFS를 한번에 이해하기 쉽게 gif 파일로 나타내주셔서 아래 링크를 첨부했습니다.

https://namu.wiki/w/BFS

#include <iostream>
#include <vector>
using namespace std;
vector<int> map[1001];    //그래프의 상태를 저장할 인접리스트
bool visit[1001];    //노드의 방문 상태를 저장할 배열
void dfs(int start) {
    visit[start] = true;    //노드를 방문
    for (int i = 0; i < map[start].size(); i++) {    //방문한 노드의 자식 노드들을 모두 방문할 때 까지 반복
        int next = map[start][i];    //자식 노드를 방문
        if (visit[next] == false) {    //방문하려는 노드가 아직 방문하지 않았으면
            dfs(next);    //재귀호출로 자식 방문
        }
    }
}

---

DFS의 가장 기본적인 개념과 코드에 대해 포스팅 했습니다.

당장 생각나는것 위주로 막 쓴 게시물이라 큰 도움이 될지 모르겠습니다만,, 

추가적으로 궁금하신 사항 댓글로 남겨주시면 답변 달아드리도록 하겠습니다!