본문 바로가기
Computer science/Data Structure

BFS vs DFS

Geoboy 2020. 12. 1. 12:29

요약

더보기

BFS와 DFS는 그래프에서 각 노드를 한 번씩만 방문하여 모든 노드를 방문하는 알고리즘이다.

BFS의 장점

1. 너비 우선 탐색이기에 찾은 답이 최단 경로임을 보장

2. 어느 한 경로가 무한히 깊어져도 최단 경로 탐색 가능

BFS의 단점

1. 간선이 많아지면 많은 메모리가 필요함

 

DFS의 장점

1. 간선이 많아져도 메모리를 많이 차지하지 않음.

2. 정답 후보군을 미리 알고 있으면 BFS보다 빠르게 구할 수도 있음.

3. 사이클 감지에 효과적

DFS의 단점

1. 구한 답이 최단 경로임을 보장하지 않음. 그래프의 모든 노드를 방문하고 난 후에야 최단 경로임을 알 수 있음.

2. 어느 한 경로가 무한히 깊으면 빠져나오지 못함.

 

BFS(Breadth First Search)와 DFS(Depth First Search)의 차이점

BFS는 queue를 이용하고 DFS는 stack을 이용한다. 

따라서 FIFO인 queue는 넓이를 우선하여 탐색하고, LIFO인 stack은 깊이를 우선하여 탐색한다.

BFS는 queue에 노드를 담을 때 방문을 체크하고, DFS는 재귀 형식으로 구현하기 때문에 stack에서 노드를 꺼내 쓸 때 방문을 체크한다.

 procedure BFS(G, root) is
      let Q be a queue
      label root as discovered
      Q.enqueue(root)
      while Q is not empty do
          v := Q.dequeue()
          if v is the goal then
              return v
          for all edges from v to w in G.adjacentEdges(v) do
              if w is not labeled as discovered then
                  label w as discovered // 큐에 넣으며 discoverd
                  Q.enqueue(w)
                  
          print v
procedure DFS(G, v) is
    label v as discovered // v를 꺼내고 discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)
            
    print v

BFS를 사용하면 ABCDEF가 출력될 것이고, DFS를 사용하면 ADFCEB가 출력될 것이다. 

 

 

DFS는 재귀를 타고 다시 거슬러 올라가기 때문에, 행위를 하고 다시 원래 상태로 돌아가야 할 때 쓰면 좋다.

예를 들어, 게임을 시뮬레이션할 때, 여러 가지 행위 중 어떤 행위를 할까 고민될 때가 있다.

공격하고 막았으면 이겼을까? 공격하고 공격하고 막았으면 이겼을까? 막고 공격했으면 이겼을까?

이 경우 DFS를 이용해 모든 경우의 수를 체크해볼 수 있다.

1  procedure DFS(actions) is
2      
3     if(actions.length == 3) {
4         canWin(actions);
5         return;
6      }
7      
8     actions.push(attack);
9     recursively call DFS(actions)
10    actions.pop();
11    actions.push(defense);
12    recursively call DFS(actions)
13    actions.pop(defense);

DFS를 3번 진행한다고 하면 8번 행에서 재귀하여 DFS의 actions는 [attack]이 되고, 다시 8번 행에서 재귀하여 [attack, attack]이 된다. 3번 째도 8번에서 [attack, attack, attack]이 되고, 길이가 3이 되어 [attack, attack, attack]으로 이길 수 있는지 확인한 후 리턴한다.

 

return으로 DFS를 빠져 나오며 9번 행으로 가고 attack을 pop 해 [attack, attack]이 된다. 그리고 10번 행에서 다시 [attack, attack, defense]가 된 actions로 12번 행에서 DFS를 호출한다. 

 

이 과정을 반복하면 모든 경우의 수를 탐색할 수 있다.

 

재귀함수는 함수 호출이 stack에 계속 쌓이기 때문에 성능상 좋지 않다.

따라서 DFS를 while문을 이용해 구현할 수도 있다.

procedure DFS_iterative(G, v) is
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do 
                S.push(w)

 

BFS는 DFS에 비해 더 많은 메모리를 사용한다. 

1번에서 6번까지 가는 가장 짧은 경로를 구하는 프로그램을 BFS와 DFS를 이용해 작성한다고 생각해보자.

BFS는 6번에 전방위 적으로 접근한다. 

1 - 2

1 - 4

1 - 7

1 - 2 - 3 (1 - 2의 메모리를 불러오고 3을 방문)

1 - 2 - 5 (1 - 2의 메모리를 불러오고 5를 방문)

1 - 7 - 6

(1 - 7 - 6에서 끝났지만 계속 프로그램을 작동시킨다면)

1 - 2 - 3 - 6 (1 - 2 - 5의 메모리를 불러오고 6을 방문)

즉, 모든 경로에 대한 정보(가중치 등)를 저장해야 한다.

 

하지만 DFS를 사용하면

1 - 2 - 3 - 6 경로에 대한 메모리 저장

1 - 2 - 5 - 6 경로에 대한 메모리 저장

1 - 7 - 6 경로에 대한 메모리 저장

...

이렇게 한 번에 한 가지 경로에 대한 정보만 저장하면 된다.

 

티스토리툴바