DFS - 깊이우선탐색

특정 노드에서부터 더이상 간선이 존재하지 않는 부분까지 탐색하는 방식

DFS는 깊이 우선 탐색 알고리즘이며, 스택이나 재귀 함수를 사용하여 구현된다
DFS는 그래프의 구성 요소, 사이클, 위상 정렬 등을 찾는 데 유용하다

순서의 예시는 아래와 같다

---

구현

1. 그래프의 구현

우선 그래프는 인접리스트, 인접행렬의 방식으로 구현된다
해당 문서에서는 인접리스트 방식을 이용하였다

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

2. DFS 함수 구현

기본적인 구조는 다음과 같다

• 탐색 시작 노드를 stack에 넣고 방문처리를 한다
• 스택의 top에 존재하는 노드는 모든 인접한 노드의 방문을 끝내지 않은 노드를 의미한다
  그러므로 노드를 stack에 넣고 방문처리 한다
• 만약 해당 노드에 대해 모든 인접한 노드를 방문한 경우 스택에서 최상단 노드를 꺼낸다

아래 코드의 경우에는 이미 방문한 스택을 확인하는데 있어 배열을 사용하면 최악의 경우 O(N)의 시간복잡도를 가지기 때문에 별도의 Set를 이용해 탐색 시간을 줄이는 방법을 채택한다

func dfs(_ graph: [String:[String]], _ start: String) -> [String] {
    var visitedRecord: Set<String> = []
    var needVisit: [String] = [start]
    var result:[String] = []
    
    while !needVisit.isEmpty {
        let node = needVisit.removeLast()
        if !visitedRecord.contains(node) {
            visitedRecord.insert(node)
            result.append(node)
            needVisit += graph[node] ?? []
        }
    }
    return result
}

전체 코드

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

func dfs(_ graph: [String:[String]], _ start: String) -> [String] {
    // 방문을 완료한 노드 저장
    // -> 방문 여부의 확인 시간을 줄이기 위한 set
    var visitedRecord: Set<String> = []
    
    // 인접 노드의 방문이 완료되지 않는 노드를 기록
    // top에 위치한 노드에서 인접 노드를 탐색해야 한다
    var needVisit: [String] = [start]
    
    // 방문 순서를 저장하기 위한 result
    var result:[String] = []
    
    // 방문해야할 노드가 사라질때까지 반복
    while !needVisit.isEmpty {
        // 방문의 필요가 있는 노드를 top에서(in stack) 꺼내 변수에 저장
        let node = needVisit.removeLast()
        // 해당 노드를 방문한적이 없으면 인접한 노드를 탐색
        if !visitedRecord.contains(node) {
            // 해당 노드를 방문처리
            visitedRecord.insert(node)
            result.append(node)
            
            // 탐색이 필요한 노드들을 그대로 더한다
            // 만약 모든 인접 노드를 방문한 경우 빈 배열을 더한다
            needVisit += graph[node]?.reversed() ?? []
        }
    }
    
    return result
}


print(dfs(graph, "A")) // 결과 : ["A", "B", "E", "C", "F", "D"]