[이코테_코딩테스트] BFS (Breadth-First Search)

date

Jul 23, 2023

slug

coding-test-bfs

author

status

Public

BFS (Breadth-First Search)

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

BFS는 큐 자료구조를 이용

동작 과정

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

큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

더 이상 2번의 과정을 수행할 수 없을 때까지 반복

BFS 동작 예시

[Step 0] 그래프 준비 (방문 기준 : 번호가 낮은 인접 노드부터라고 가정)

시작 노드 : 1

[Step 1] 시작 노드인 ‘1’을 큐에 삽입 & 방문 처리

[Step 2] 큐에서 노드 ‘1’을 꺼내 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’을 큐에 삽입 & 방문 처리

[Step 3] 큐에서 노드 ‘2’를 꺼내 방문하지 않은 인접 노드 ‘7’을 큐에 삽입 & 방문 처리

[Step 4] 큐에서 노드 ‘3’을 꺼내 방문하지 않은 인접 노드 ‘4’, ‘5’를 큐에 삽입 & 방문 처리

[Step 5] 큐에서 노드 ‘8’을 꺼냄 & 방문하지 않은 인접 노드가 없으므로 무시

위 과정을 반복하였을 때 전체 노드의 탐색 순서(큐에 들어간 순서)

탐색 순서 : 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6

BFS 소스코드 예제 (Python)


from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

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

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

이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 3. DFS & BFS” 영상을 보고 작성하였습니다.