BFS/DFS 간단 예제 - Swift

 

 

개념

 

 

 

BFS (Breath First Search)

• 너비 우선 순회
• queue로 구현 (queue를 활용하기 때문에 FIFO)
•  
• 장점 : 최적해를 찾을 것을 보장한다
• ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현 후, 짱구와 철수 사이의 관계 경로를 찾는 경우
  • BFS : 짱구와 가까운 관계부터 살핀다
  • DFS : 지구 상 모든 관계를 다 살펴봐야할지도,,
• 로직
  1. 시작 노드를 큐에 삽입하고 방문처리
  2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리
     (방문하면 현재 위치는 pop해주고 방문처리 -> 방문할 곳은 queue에 넣음)

 

 

 

---

 

DFS (Depth First Search)

• 깊이 우선 순회
• stack과 재귀 함수로 구현
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용
• BFS보다 조금 더 간단하게 구현 가능
• 검색 속도 자체는 BFS에 비해서 느림
• 장점
  • 현재 경로의 노드들만 기억하면 되므로 저장공간을 상대적으로 적게 사용함
  • 목표 노드가 깊은 곳에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로를 깊게 탐색할 경우 오래 걸림
  • 최적해가 아닐 가능성이 있다
• ex) 미로찾기 시 최대한 한방향으로 쭉 가다가 막다른 길일 때 가장 가까운 갈림길로 돌아와 그 갈림길 부터 다시 탐색
• 로직:
  1. 시작 노드를 true로 바꿈
  2. 인접한 노드 사이즈만큼 탐색한다
  3. 방문하지 않았으면 재귀적으로 방문

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

 

 

공통점

• 두 가지 모두 그래프를 탐색하는 방법이다.

* 그래프 
: node(정점)과 그 노드를 연결하는 edge(간선)으로 이루어진 자료구조.
하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하는 것을 탐색이라 한다.

* 주의
그래프를 탐색할 때, 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다.
그렇지 않으면 무한루프에 빠질 위험이 있다.

 

 

 

 

 

 

---

 

 

 

Queue 구현 코드를 모른다면 펼쳐보기

public struct Queue<T> {
  fileprivate var array = [T]()
  
  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  public var count: Int {
    return array.count
  }
  
  public mutating func enquque(_ element: T) {
    array.append(element)
  }
  
  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }
  
  public var front: T? {
    return array.first
  }
}

 

 

예제에서 사용할 그래프와 visited 배열

let graph = [
    [], // 0
    [2,3], // 1
    [1,4,5], // 2
    [1,6,7], // 3
    [2], // 4
    [2], // 5
    [3], // 6
    [3,8], // 7
    [7] // 8
]

var visited = Array.init(repeating: false, count: graph.count)

 

 

DFS

// dfs
func dfs(start: Int) {
  visited[start] = true // 시작점
  
  print(start, terminator: " ")
  
  for i in graph[start] { // 왼쪽부터 순회
    if !visited[i] {
      dfs(start: i)
    }
  }
}

dfs(start: 1)

// 출력결과
// 1 2 4 5 3 6 7 8

 

 

BFS

var queue = Queue<Int>()
// bfs
func bfs(start: Int) {
  queue.enquque(start) // 시작점 큐에 넣기
  visited[start] = true // 시작점 방문으로 체크
  
  while !queue.isEmpty {
    guard let elem = queue.dequeue() else { return }
    print(elem, terminator: " ")
    
    for i in graph[elem] {
      if !visited[i] {
        queue.enquque(i)
        visited[i] = true
      }
    }
  }
}

// 출력결과
// 1 2 3 4 5 6 7 8

 

 

 

 

참고링크

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog