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

DFS(깊이 우선 탐색) 알고리즘의 개념

 

트리 혹은 그래프를 탐색하는 기법 중 하나로 시작 노드에서 자식의 노드들을 순서대로 탐색을 하면서 가장 깊은 곳을 우선으로 탐색하는 알고리즘 입니다. 백트래킹에 사용하는 대표적인 탐색 알고리즘입니다.

재귀함수 또는 Stack 으로 구현 가능합니다.

 

DFS 탐색 과정

 

스텍을 사용하였을때 구현 과정을 설명하면은

 

1. 시작 노드 1을 방문하여 방문가능한 2 , 5 , 9 번 노드를 스텍 안에 넣습니다 [2,5,9]

2. 스텍에 있는 2번 노드를 제일 먼저 방문하여 방문 처리후 3번 노드를 스텍에 넣습니다. [3,5,9]

3. 스텍에 있는 3번 노드를 방문하여 방문 처리후 4번 노드를 스텍에 넣습니다. [4,5,9]

4. 스텍에 있는 4번 노드를 방문하여 더이상 방문 노드가 없음으로 스텍에 남아있는( [5,9] ) 5번을 방문합니다.

5. 위의 있는 과정을 반복합니다.

 

위의 과정을 통해 가장 깊은 곳을 먼저 방문하는것을 확인 할 수 있습니다.

 

 

 

아래의 코드는 재귀를 통해 구현한 DFS 문제 풀이입니다.

import Foundation

//백준 2606번
let n = Int(readLine()!)!
let m = Int(readLine()!)!

var matrix = Array(repeating: Array(repeating: 0, count: n+1), count: n+1)
var visited = Array(repeating: false, count: n+1)
var answer = 0

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map({Int(String($0))!})
    matrix[input[0]][input[1]] = 1
    matrix[input[1]][input[0]] = 1
}

func dfs(_ v : Int) {
    visited[v] = true
    answer += 1
    for i in 1..<n+1 {
        if visited[i] == false && matrix[v][i] == 1 {
            dfs(i)
           
        }
    }
    
}

dfs(1)
print(answer-1)

 

 

 

 

 

 

왜 사용해야할까 or 나만의 고민

BFS에 비해 구현이 좀더 간단합니다 ( 재귀로 구현시 간단 )

순회 중인 정점만 저장하는 스텍 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지합니다.

목표하는 곳이 깊은 단계에 있을경우에 해를 빨리 구할 수 있습니다.

 

하지만 해가 없는 경로에 깊이 빠질 가능성이 있습니다.

얻은 해가 최단경로라는 보장이 없습니다( 두 정점 사이 최단경로를 찾으려는 경우 최적의 해가 아닐수 있음 )