알고리즘2. BFS란?

BFS란

Breadth First Search로 너비 우선 탐색입니다. DFS와 마찬가지로 완전 탐색 알고리즘입니다. 그러나 탐색 순서가 DFS와 차이가 있습니다.

---

BFS 구현방법

BFS는 큐를 이용하여 구현할 수 있습니다. 큐는 FIFO(First In First Out)으로 선입선출의 구조를 갖고있습니다.

BFS의 탐색 원리

아래 그림의 숫자는 BFS의 탐색 순서입니다. BFS는 왼쪽에서 오른쪽으로 차례대로 탐색함을 알 수 있습니다.

큐라는 터미널이 있습니다. 이 터미널에는 두가지의 규칙이 존재합니다.

• 맨 앞의 노드를 밖으로 내보내기
• 나온 노드와 연결된 노드를 터미널로 넣기

아래는 큐의 동작 예시입니다.
IN: 0
OUT:
=> 0이 큐에 삽입됩니다.

IN: 1 2
OUT: 0
=> 0이 밖으로 나오고 1, 2가 큐에 삽입됩니다.

IN: 2 3 4
OUT: 1
=> 1이 밖으로 나오고 3, 4가 큐에 삽입됩니다.

이와 같은 과정이 반복됩니다.

BFS 코드

from collections import deque

adj = [[0] * 13 for _ in range(13)]  # 13 * 13의 배열 생성
adj[0][1] = adj[0][2] = 1  # 인접행 초기화 1은 연결, 0은 연결 아님
adj[1][3] = adj[1][4] = 1
adj[2][5] = adj[2][6] = adj[6][10] = adj[6][11] = adj[6][12] = 1
adj[3][7] = adj[3][8] = adj[4][9] = 1

def dfs():
  dq = deque()  # 큐 생성
  dq.append(0)  # 큐 초기화
  while dq:
    now = dq.popleft()
    print(now)
    for nxt in range(13):
      if adj[now][nxt]:  # 인접행 값이 1이면 dq에 추가
        dq.append(nxt)


dfs()  # dfs 호출