[알고리즘] DFS 구현

개념

깊이 우선 탐색으로, Depth-First-Search의 줄임말인 DFS라고 많이 부른다.

탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식이다. 

 

 

앞선 글인 BFS와 마찬가지로 숫자가 순서라고 생각하면 된다.

탐색 노드의 인접 노드의 자식 노드들을 모두 탐색하고 다시 돌아가서 탐색 노드의 다른 인접 노드의 자식 노드들을 탐색하는 방법이다. 

 

BFS와 마찬가지로,

하나의 노드에 대한 인접 노드들 중에서 왼쪽/오른쪽의 순서는 중요하지 않다.

어디를 먼저하더라도 해당 노드에서 가장 깊은 노드(자식의 .. 자식의 .. 자식 노드)를 다 탐색해야 다음 인접 노드를 탐색할 수 있기 때문이다.

 

 

구현

그래프 생성

BFS와 마찬가지로 인접 리스트 방식을 사용해서 그래프를 만들면 아래와 같다.

 

let graph: [String: [String]] = [
    "A" : ["B", "C"],
    "B" : ["A", "D", "E"],
    "C" : ["A", "F"],
    "D" : ["B"],
    "E" : ["B"],
    "F" : ["C"],
]

 

 

깊이 우선 탐색

BFS에서는 두개의 큐를 바탕으로 탐색을 구현했다.

DFS의 경우는 하나의 큐와 하나의 스택으로 구현할 수 있다.

 

✅ 방문 해야하는 노드를 저장하는 Stack 

✅ 이미 방문한 노드를 저장하는 Queue

 

그리고 아래의 과정을 반복한다.

1. 탐색할 노드의 데이터를 needVisitQueue에 넣는다.
2. needVisitQueue의 첫번째 값을 추출해서(= 큐이므로 FIFO) visitedQueue에 해당 값이 존재하는지 확인한다.
   1. 만약 visitedQueue에 추출한 값이 존재하면, 추출한 값을 버리고
   2. 다음 첫번째 값을 추출해서 다시 확인한다. 
   3. 1-2의 과정을 needVisitQueue가 비워지면 그 때 탐색이 끝나는 것이다.
3. 추출된 값이 존재하지 않으면 visitedQueue에 추가한다. 
4. 추출된 값(위에서 visitedQueue에 추가된 값)에 연결된 간선들을 모두 needVisitQueue에 추가한다.
5. 그리고 다시 2번부터 작업을 한다.

 

visitedQueue

A

C

F

B

E

D

needVisitQueue

 

결과적으로 위와 같이 큐에 저장이 된다. 

 

이 과정을 코드로 구현하면 아래와 같다.

func DFS(graph: [String: [String]], start: String) -> [String] {
    var visitedQueue: [String] = []
    var needVisitStack: [String] = [start]
    
    while !needVisitStack.isEmpty {
        let node: String = needVisitStack.removeLast()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
       needVisitStack += graph[node] ?? []
    }
    
    return visitedQueue
}

 

BFS와 거의 똑같고, 큐가 아닌 스택으로 구현되었기 때문에 removeFirst가 아니라 removeLast로 구현을 해야 한다.

 

 

시간 복잡도

일반적으로 노드 수(V), 간선 수(E)라 했을 때 시간 복잡도는 O(V+E)이다. (입력 자체를 노드와 간선을 기준으로 받기 때문이다.)