DFS

깊이 우선 탐색(DFS)

Depth-First Search

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

 

한개의 큐와 한개의 스택으로 구현

방문해야하는 노드 저장 스택(LIFO)

이미 방문한 노드를 저장하는 큐 (FIFO)

 

1. 탐색 노드 큐에 스택에 담기

2. 스택에 마지막 값을 추출해 큐에 존재하는지 확인

3. 큐에 존재하면 존재하지 않는게 나올때까지 확인 후 큐에 추가

4. 큐에 추가된 값의 연결된 간선들 모두 스택에 추가

* 스택이 빌때까지 2번부터 반복

 

 

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