DFS(깊이 우선탐색)

깊이 우선탐색이란?

• 그래프를 탐색할 때 쓰이는 알고리즘
• 특정한 노드에서 가장 멀리 있는 노드를 먼저 탐색하는 알고리즘
• 주어진 맵전체를 탐색하며 한번 방문한 노드는 다시 방문하지 않는다.

// 수도코드
DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)

• 어떠한 정점 u의 visited를 참으로 바꾸고 u로부터 연결되어 있는 v지점을 탐색한다.
• 방문되어 있지 않은 노드에 대해 재귀적으로 DFS를 호출.

출처) https://m.blog.naver.com/jhc9639/222289089015?referrerCode=1

1번 노드에서 시작하여 4번노드까지 가장 멀리 떨어져있는 정점까지 방문한 다음 그 다음 정점들을 차례로 방문한다.

 

DFS 구현방법 - 1

void dfs(int here){
    visited[here] = 1; 
    for(int there : adj[here]){
        if(visited[there]) continue;
        dfs(there);
    }
}

• 방문했다면(visited[there])라면 방문하지 않고 방문 안했다면 방문한다.
• 해당 there에 대해서 dfs를 호출하는 방법

 

DFS 구현방법 - 2

void dfs(int here){
    if(visited[here]) return;
    visited[here] = 1;
    for(int there : adj[here]){ 
        dfs(there);
    }
}

• 방문 여부에 상관없이 일단 DFS를 호출한다.
• 해당 함수에서 방문했다면 return을 통해 함수를 종료한다.