깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) Swift

출처:https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89

깊이 우선 탐색(DFS)

- 루트노드에서 시작하여 다음 분기로 넘어가기전 해당 분기를 완벽하게 탐색하는 방법.

- 해당 분기를 모두 탐색한 후, 이 분기는 이미 탐색함을 기록하고 다음분기로 넘어감

- 백트래킹으로 이용한다.

- 스택 또는 재귀함수로 구현한다.

-> 모든 노드를 방문하고자 할때 주로 사용함

-> BFS에 비해 상대적으로 검색속도가 느림

-> 구현은 DFS가 더 간단하다.

 

너비 우선 탐색(BFS)

- 루트노드 혹은 임의노드부터 시작하여 인접한 가까운 노드부터 탐색하고 마지막으로 가장 먼 노드를 탐색하는 방법

- 주로 노드사이의 최단거리를 계산할때 사용한다.

- 큐로 구현한다.

 

ex) 지구상의 모든 관계를 그래프로 표현했을때, 철수와 영희와의 관계를 찾는다면

깊이 우선탐색: 모든 관계를 탐색하며 찾는다.

너비 우선탐색: 철수의 가까운 관계부터 찾는다.

 

DFS와 BFS의 시간복잡도

모든 노드를 탐색한다는점에서 DFS와 BFS의 시간복잡도는 동일하다.

구현할때의 이용한 자료구조에 따라서 전체 시간복잡도는 다르게 될 수 있다.

N은 노드, E는 걸리는 시간 이라 한다면

인접리스트: O(N+E)

인접행렬: O(N^2)

 

DFS와 BFS의 활용유형

1. 그래프의 모든 접점을 방문해야 할 때

- 이는 둘다 비슷한 성능을 내므로 알맞은 자료구조로 시간을 줄여서 구현한다.

 

2. 경로의 특징을 저장해야할 때

- 백트래킹과 같은 노드를 탐색했을때, 조건에 맞지않아서 이를 기록하고 더이상 노드탐색을 하지않을때나 탐색하는데 있어서 여러가지 특징이나 조건을 저장하고 탐색할때 DFS를 이용한다.

 

3. 최단거리를 구할 때

- 미로찾기와 같은 최단거리를 구할 때 BFS를 이용하면 좋다.

- DFS를 이용한다면 모든 노드를 방문하게 될 수 있기때문이다.

 

DFS 구현 Swift

// 소스코드 출처: 개발자 소들이 https://babbab2.tistory.com/107

func dfs(graph: [String: [String]], start: String) -> [String]{
    // 이미 방문한 배열
    var visitedQueue = [String]()
    // 방문해야하는 배열
    var needVisitQueue = [start]
    
    // DFS
    // 분기에 가장 깊숙한 곳까지 탐색하기 때문에 removeLast()
    while !needVisitQueue.isEmpty {
        let node = needVisitQueue.removeLast()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
        needVisitQueue += graph[node] ?? []
    }
    return visitedQueue
}

 

BFS 구현 Swift

// 소스코드 출처: 개발자 소들이 https://babbab2.tistory.com/106

func bfs(graph: [String: [String]], start: String) -> [String]{
    // 이미 방문한 배열
    var visitedQueue = [String]()
    // 방문해야하는 배열
    var needVisitQueue = [start]
    
    // BFS
    // 분기에 가장 인접한 곳 부터 탐색하기 때문에 removeFirst()
    while !needVisitQueue.isEmpty {
        let node = needVisitQueue.removeFirst()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
        needVisitQueue += graph[node] ?? []
    }
    return visitedQueue
}

 

 

Reference:

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

DFS, BFS의 설명, 차이점

https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

https://babbab2.tistory.com/107

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