[알고리즘] BFS(넓이 우선 탐색)-큐(Queue)

BFS란?

DFS와 함께 대표적인 그래프 탐색 알고리즘이다. BFS는 넓이 우선 탐색(Breadth First Search)이라는 알고리즘이며, 정점에서 가까운 노드부터 우선적으로 탐색한다.

• BFS는 Queue라는 자료구조를 이용하여 구현할 수 있다.
  • 탐색 시작 노드를 Queue에 삽입하고 방문 처리를 한다.
  • Queue에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에 방문하지 않은 노드들을 모두 Queue에 삽입하고, 방문 처리 해준다.
  • Queue에 남은 요소가 없을 때까지 반복해준다.

# 순회 경로 출력 (인접 행렬)
from collections import deque

def bfs(start_node):
    queue = deque([start_node])
    used = [False] * 4
    used[start_node] = True

    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for i in range(len(arr[node])):
            if arr[node][i] == 1:
                if used[i] == False:
                    used[i] = True
                    queue.append(i)
arr = [
    [0, 1, 1, 0],
    [0, 0, 1, 1],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]

bfs(0)

# 순회 경로 출력 (인접 행렬)
from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
graph = [
  [1,2],
  [2, 3],
  [3],
  []
]

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

• BFS 알고리즘 문제💡
  • 백준 스타트링크
  • 백준 아기상어2