[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(5) - BFS, BFS와 DFS의 특징 및 정리

#책 페이지 

p.143

 

#탐색 알고리즘 BFS에서 사용하는 자료구조

큐 자료구조

 

#BFS는 어떻게 동작할까?

👉BFS는 '너비 우선 탐색 알고리즘' 이다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색한다면 BFS는 반대이다. 

인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. 

 

👉BFS는 큐 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. 

① 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

② 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 

①,② 번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

 

┌동작과정을 아래와 같이 그림으로 표현해보았다.

 

 

 

 

 

 

▲결과적으로 노드의 탐색 순서(=큐에 들어간 순서) 는 다음과 같다. 1->2->3->8->7->4->5->6

 

#BFS의 시간복잡도

BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 구현함에 있어 deque라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요된다. 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이라는 점까지만 추가로 기억하자. 

 

⭐재귀함수로 DFS를 구현하면 컴퓨터 시스템의 특성상 실제 프로그램의 수행 시간이 느려질 수 있다. 따라서 스택 라이브러리를 이용해 시간 복잡도를 완화하는 테크닉이 필요할 때도 있다. 다만, 이 내용은 책의 범위를 벗어나므로 코딩테스트에서는 보통 DFS보다는 BFS 구현이 조금 더 빠르게 동작한다는 정도로 기억하자. 

 

#BFS 구현 예제

from collections import deque

#BFS 메서드 정의
def bfs(graph, start, visited) :
    #큐 구현을 위해 deque라이브러리 사용
    queue=deque([start])
    #현재 노드를 방문 처리
    visited[start]=True
    #queue가 빌 때까지 반복
    while queue :
        #큐에서 하나의 원소를 뽑아 출력
        v=queue.popleft()
        print(v, end=' ')
        for i in graph[v] :
            if not visited[i] :
                queue.append(i)
                visited[i]=True

#각 노드가 연결된 정보를 리스트 자료형으로 표현한다(2차원)
graph=[
    [], #노드는 보통 1번부터 시작하니 비워두자.
    [2,3,8], #1번 노드
    [1,7], #2번 노드
    [1,4,5], #3번 노드
    [3,5], #4번 노드
    [3,4], #5번 노드
    [7], #6번 노드
    [2,6,8], #7번 노드
    [1,7] #8번 노드
]

#각 노드가 방문한 정보를 리스트 자료형으로 표현(1차원 리스트)
visited=[False]*9

#정의 된 BFS 함수 호출
bfs(graph, 1, visited)

'''
결과
1 2 3 8 7 4 5 6 
'''

▲설명

여기서 알아두어야 할 것은 collections 모듈의 deque라이브러리이다.

리스트의 연산 중 pop(0)은 시간복잡도 O(N)을 가지는데 반해 deque의 popleft()는 같은 기능을 하면서도 O(1)의 시간복잡도를 가지기 때문에 큐는 deque로 구현하면 좋다. 

 

 

#DFS와 BFS 비교 

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

 

#문제 적용

맵이 3x3 형태의 2차원 배열이고 각 데이터를 좌표라고 생각한다면 그래프로(노드와 간선) 바꾸어 풀수 있도록 하자.