BFS와 DFS

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

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

 

최단 경로나 순위 선정 같은 문제에서 만날 수 있는 탐색 알고리즘들이다.

그래프의 개념과 표현법(인접 리스트, 인접 행렬)에 대해서는 아래 글을 참고하면 된다.

one-step-a-day.tistory.com/116

간단한 예시를 통해 각 방법이 어떻게 그래프를 탐색하는지 보자.

아래와 같이 트리가 주어진다고 하자.

 

7개의 정점과 6개의 간선을 가진 트리

BFS와 DFS를 사용하여 전체 트리를 탐색하는 과정을 보자. 특정 노드에 도착하면 노드의 색을 칠한다.

 

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

 

  주어진 트리를 BFS로 방문하는 과정은 위 그림과 같다. BFS의 경우 Level을 기준으로 탐색을 진행하게 된다.

Level 1 탐색이 완료되면 Level 2를 순차적으로 탐색하고, Level 2 탐색이 완료되면 Level 3를 탐색한다. (이 때 각 Level에서 오른쪽부터 검색할지, 왼쪽부터 검색할지는 알고리즘에 따라 달라진다.)

 

트리의 레벨

위와 같은 탐색을 진행하려면 다음과 같이 시작하면 된다.

 

1. 시작 노드를 방문한다.(Level 1)

2. 방문한 노드의 자식 노드들을 추가한다.(Level 2)

3. 추가된 자식 노드들을 차례로 방문하며 손자 노드들을 추가한다(Level 3)

4. 추가된 손자 노드들을 차례로 방문한다.

 

위와 같은 기능은 큐로 아래와 같이 구현할 수 있다.

 

1. 우선 빈 큐를 생성한 뒤 시작 노드를 추가한다.

2. 큐가 비어있지 않은 경우 아래 과정을 반복한다.

3. (Loop Start) 큐에서 Dequeue한다.(큐의 Front에 있는 원소를 pop) 

4. Dequeue한 원소의 자식 노드들을 큐에 append한다. (Loop end)

5. 큐가 비어있으면 종료한다.

 

위를 코드로 구현하면 아래와 같다. Visited를 표시하는 이유는 방문한 곳을 다시 방문하지 않기 위함이다.

(하나의 자식 노드가 2개의 부모 노드를 갖는 경우 중복 탐색이 발생할 수 있다.)

 

def bfs(arr, start):
    visited = defaultdict(bool)
    deq = deque([start])
    answer = []
    visited[start] = True
    while deq:
        x = deq.popleft()
        answer.append(x)
        for i in v_list[x]:
            if visited[i] == False:
                visited[i] = True
                deq.append(i)
    return answer

DFS(Depth-First-Search) : 너비 우선 탐색

BFS는 트리의 Level 순서대로 방문하는 알고리즘이었다면, DFS는 경로 순서대로 끝까지 탐색하는 알고리즘이다.

DFS로 위에서 주어진 노드 방문 순서는 아래와 같다.

처음 방문한 노드를 기준으로 모든 경로들을 따라나간 뒤, 다음 노드를 방문한다.

 

DFS는 스택을 사용하여 아래와 같이 구현할 수 있다.

 

1. 우선 빈 스택를 생성한 뒤 시작 노드를 추가한다.

2. 스택이 비어있지 않은 경우 아래 과정을 반복한다.

3. (Loop Start) 스택에서 pop한다.(스택의 Top에 있는 원소를 pop)

4. pop한 원소의 자식 노드들을 스택에 append한다. (Loop end)

5. 큐가 비어있으면 종료한다.

 

위의 코드를 구현해보면 아래와 같다.

 

def dfs(arr, start):
    visited = defaultdict(bool)
    stk = [start]
    answer = []
    while stk:
        x = stk.pop()
        if visited[x] == False:
            visited[x] = True
            answer.append(x)
            stk.extend(v_list[x][::-1])
    return answer