잔재미코딩

너비 우선 탐색 (BFS)

파이썬을 활용하여 자동화 프로그램 만들기

혹시 자료가 도움이 되셨다면, 제가 특별히 만든 파이썬 기본을 업무 자동화 기술까지 함께 익혀보실래요?

파이썬 스펙을 쌓으세요. 패턴과 템플릿으로 정말 쉽게 만들었습니다.

프로그래밍을 익혀보셨다 실패하셨다면! 꼭 한번 이 강좌로 시도해보세요! 1:1 코칭까지!

자세히 알아보기

3. 너비 우선 탐색 (Breadth-First Search)

1. BFS 와 DFS 란?

  • 대표적인 그래프 탐색 알고리즘
    • 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
    • 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식

BFS/DFS 방식 이해를 위한 예제

  • BFS 방식: A - B - C - D - G - H - I - E - F - J
    • 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함
  • DFS 방식: A - B - D - E - F - C - G - H - I - J
    • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함

2. 파이썬으로 그래프를 표현하는 방법

  • 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음

그래프 예와 파이썬 표현

In [4]:
graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
파이썬을 활용하여 자동화 프로그램 만들기

혹시 자료가 도움이 되셨다면, 제가 특별히 만든 파이썬 기본을 업무 자동화 기술까지 함께 익혀보실래요?

파이썬 스펙을 쌓으세요. 패턴과 템플릿으로 정말 쉽게 만들었습니다.

프로그래밍을 익혀보셨다 실패하셨다면! 꼭 한번 이 강좌로 시도해보세요! 1:1 코칭까지!

자세히 알아보기
In [5]:
graph
Out[5]:
{'A': ['B', 'C'],
 'B': ['A', 'D'],
 'C': ['A', 'G', 'H', 'I'],
 'D': ['B', 'E', 'F'],
 'E': ['D'],
 'F': ['D'],
 'G': ['C'],
 'H': ['C'],
 'I': ['C', 'J'],
 'J': ['I']}

3. BFS 알고리즘 구현

  • 자료구조 큐를 활용함
    • need_visit 큐와 visited 큐, 두 개의 큐를 생성

  • 큐의 구현은 간단히 파이썬 리스트를 활용
In [9]:
data = [1, 2, 3]
data.extend([4, 5])
data
Out[9]:
[1, 2, 3, 4, 5]
In [12]:
def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited
In [13]:
bfs(graph, 'A')
Out[13]:
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

파이썬을 활용하여 자동화 프로그램 만들기

혹시 자료가 도움이 되셨다면, 제가 특별히 만든 파이썬 기본을 업무 자동화 기술까지 함께 익혀보실래요?

파이썬 스펙을 쌓으세요. 패턴과 템플릿으로 정말 쉽게 만들었습니다.

프로그래밍을 익혀보셨다 실패하셨다면! 꼭 한번 이 강좌로 시도해보세요! 1:1 코칭까지!

자세히 알아보기

4. 시간 복잡도

  • 일반적인 BFS 시간 복잡도
    • 노드 수: V
    • 간선 수: E
      • 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
    • 시간 복잡도: O(V + E)
In [15]:
def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    count = 0
    while need_visit:
        count += 1
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    print (count)
    return visited
In [16]:
bfs(graph, 'A')

19
Out[16]:
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

깊이 우선 탐색 (DFS) 탐욕 알고리즘의 이해