본문 바로가기
Algorithm

DFS(깊이 우선탐색)

by 곰제비 2022. 6. 24.

깊이 우선탐색이란?

  • 그래프를 탐색할 때 쓰이는 알고리즘
  • 특정한 노드에서 가장 멀리 있는 노드를 먼저 탐색하는 알고리즘
  • 주어진 맵전체를 탐색하며 한번 방문한 노드는 다시 방문하지 않는다.
// 수도코드
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을 통해 함수를 종료한다.

'Algorithm' 카테고리의 다른 글

Prefix sum(누적합)  (0) 2022.06.20
Recursion Function(재귀 함수)  (0) 2022.06.20
Time Complexity(시간 복잡도)  (0) 2022.06.20
Selection Sort(선택 정렬)  (0) 2022.06.14
GCD(최대공약수), LCM(최소공배수) C++ 구현  (0) 2022.06.14