[Swift] 깊이우선탐색(DFS) 구현해보기

이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다.

자세한 내용은 https://babbab2.tistory.com/107 이곳을 확인해주세요!

 

깊이우선탐색(DFS)

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

출처: https://babbab2.tistory.com/107

탐색 노드의 인접 노드의 자식 노드들을 모두 탐색하고, 다시 돌아가서 다른 인접노드의 자식들을 모두 탐색합니다.

탐색 노드의 가장 깊은 높드까지 다 탐색해야 다음 인접노드를 탐색할 수 있습니다.

 

구현

탐색할 그래프 미리 만들어두기

출처: https://babbab2.tistory.com/107

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

깊이우선탐색을 하는 방법

깊이우선탐색은 한개의 큐(Queue)와 한개의 스택(Stack)으로 구현합니다.

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

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

출처: https://babbab2.tistory.com/107

1. 탐색할 노드의 데이터를 needVisitStack에 넣습니다.
2. needVisitStack의 마지막 값을 추출해서, visitedQueue에 해당하는 값이 존재하는지 확인합니다.
[존재하는 경우] - 추출한 값은 버리고 그 다음 마지막 값을 다시 추출하여 visitedQueue에 존재하는 지 확인합니다.
[존재하지 않는 경우] - 3번 과정으로 넘어갑니다.
3. 추출된 값이 visitedQueue에 존재하지 않으면, visitedQueue에 추가합니다.
4. 추출된 값에 연결된 간선들을 모두 needVisitStack에 추가합니다.
5. needVisitStack이 빌 때까지 2번부터 반복합니다.
6. needVisitStack이 모두 비었을 경우 visitedQueue에 채워진 값들이 탐색된 노드들의 순서인 것으로 결론 짓습니다.

코드

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
}

깊이우선탐색(DFS)의 시간 복잡도

일반적으로 노드 수(V), 간선 수(E)라 했을 때 시간복잡도는 O(V+E)입니다.

입력 자체를 노드와 간선으로 받기 때문에 그렇습니다.