DFS, BFS에 대해 알아봅시다.

안녕하세요. KataRN입니다.

 

오늘은 DFS, BFS에 대해 알아보겠습니다.

 

DFS : Depth First Search(깊이 우선 탐색)

weigh을 가지지 않는 방향 그래프에서 모든 경우를 구해볼 때 이 DFS를 사용됩니다.

예를 들면 1부터 N까지의 자연수 중 n개의 집합을 만들 수 있을 때, 가능한 모든 순열을 구해야 할 때 사용할 수 있습니다.

스택을 통해 구현하며, 재귀함수를 통해 구현합니다.(함수가 호출되면 스택 영역에 쌓이게 된다. 효율성이 떨어지는 이유)

코드로 확인해 볼게요.

func practiceDFS(numbers: [Int], m: Int) {
    // 1. 궁극적으로 구하고자 하는 값. 재귀 함수의 외부에 선언되었다. 재귀 함수를 돌며 특정 기준에 만족할 경우 이 값을 변경할 것이다.
    var result = Array<[Int]>()
    
    func dfs(selected: [Int]) {
        guard selected.count < m else {
            // 2 재귀를 멈추는 조건. 재귀 함수를 돌다가 특정 조건(요구를 만족하는 조건)에 다다르면 재귀 함수를 종료한다.
            result.append(selected)
            return
        }
        for number in numbers {
            guard selected.contains(number) == false else { continue }
            dfs(selected: selected + [number])
        }
    }
    // 3. 재귀함수를 호출할 때의 초기값. 어디서부터 연산을 시작할지는 중요하다.
    dfs(selected: [])
    print(result)
}
practiceDFS(numbers: [1,2,4], m: 2)
// print "[[1, 2], [1, 4], [2, 1], [2, 4], [4, 1], [4, 2]]"

위와 같이 3가지로 분류해서 생각하면 쉬운것 같습니다.

 

예제 하나 더 추가하겠습니다.

func dfs(graph : [String:[String]], startNode : String) -> [String] {
    var visitedQueue : [String] = []
    var needVisitQueue : [String] = []
    
    needVisitQueue.append(startNode)
    
    while needVisitQueue.count != 0 {
        let node = needVisitQueue.removeLast()
        if !visitedQueue.contains(node) {
            visitedQueue.append(node)
            needVisitQueue.append(contentsOf: graph[node]!)
        }
    }
    return visitedQueue
}

 

 

BFS : Breadth First Search(너비 우선 탐색)

weigh을 가지지 않는 방향 그래프에서 최단/최소 경로를 구해볼 때 이 BFS를 사용됩니다.

큐를 통해 구현됩니다.

func bfs(graph : [String:[String]], startNode : String) -> [String] {
    var visitedQueue : [String] = []
    var needVisitQueue : [String] = []
    
    needVisitQueue.append(startNode)
    
    while needVisitQueue.count != 0 {
        let node = needVisitQueue.removeFirst()
        if !visitedQueue.contains(node) {
            visitedQueue.append(node)
            needVisitQueue.append(contentsOf: graph[node]!)
        }
    }
    return visitedQueue
}

 

최근에 문제를 풀다보니 저는 아무리 생각해도 DFS인거 같은데... 다른분의 풀이가 BFS인겁니다...

그래서 아래의 내용을 찾게되었습니다...

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.

단지 특화된 장점들이 있고 그곳에 쓰면 더 빠르게 일처리가 될뿐입니다.

 

사실 BFS와 DFS는 코드가 한줄 다릅니다."removeFirst" or "removeLast" 입니다.

그래서 바로 바꿔서 썼더니 똑같이 통과되더라구요.

결국 제가 풀었던 문제는 상관이 없었던 문제였던겁니다.

 

여러분도 아래를 참고해서 적용합시다.

• 경로의 특징을 저장해둬야 하는 문제
  예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 최단거리 구해야 하는 문제
  미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
  왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
  너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

 

 

사실  아직 저도 이해를 못한지라... 좀더 공부해서 글 수정해놓겠습니다.

 

아래 블로그에 더 자세히 설명되어있습니다.

 

오늘도 읽어주셔서 감사합니다.

 

출처 : https://wlaxhrl.tistory.com/88?category=842165 

Swift로 그래프 탐색 알고리즘을 실전 문제에 적용해보기 - DFS 편

 

출처 : https://haningya.tistory.com/374

Graph Swift (BFS, DFS)