그래프 탐색하기 위한 대표적인 알고리즘 DFS/BFS - BFS란?

 

1. BFS (Breadth First Search)

BFS는 '너비 우선 탐색' 알고리즘으로, 가까운 노드부터 탐색하는 방식이다.

DFS가 깊이 우선으로 탐색하는 것과 달리, BFS는 탐색 시작 노드에서 가까운 노드를 먼저 방문하고 점점 멀리 있는 노드를 방문한다. 

 

BFS의 구현에서는 선입선출(FIFO) 구조인 큐(Queue)를 사용한다. 

인접한 노드를 큐에 삽입하면, 먼저 들어온 노드가 먼저 처리되므로 가까운 노드부터 탐색하게 된다. 

 

 

<BFS 동작 과정>

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내고, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

 

<BFS 예시 설명>

아래 그래프에서 노드 1을 시작 노드로 BFS를 실행해보자.

 

step1. 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다. 

• 방문 처리된 노드는 회색
• 큐에서 꺼내 현재 처리하는 노드는 하늘색
• 큐: [1], 방문 노드: {1}

 

step2. 큐에서 노드 '1'을 꺼내고 방문하지 않은 인접 노드 '2', '3', '8'을 모두 큐에 삽입하고 방문 처리를 한다.

• 큐: [2,3,8], 방문 노드: {1,2,3,8}

 

step3. 큐에서 노드 '2'를 꺼내고 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문 처리를 한다.

• 큐: [3,8,7], 방문 노드: {1,2,3,8,7}

 

step4. 큐에서 노드 '3'을 꺼내고 방문하지 않은 인접 노드 '4', '5'를 모두 큐에 삽입하고 방문 처리를 한다.

• 큐: [8,7,4,5], 방문 노드: {1,2,3,8,7,4,5}

 

step5. 큐에서 노드 '8'을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.

• 큐: [7,4,5], 방문 노드: {1,2,3,8,7,4,5}

step6. 큐에서 노드 '7'을 꺼내고 방문하지 않은 인접 노드 '6'을 큐에 삽입하고 방문 처리를 한다.

• 큐: [4,5,6], 방문 노드: {1,2,3,8,7,4,5,6}

step7. 남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 최종적으로 다음과 같다.

• 큐: [], 방문 노드: {1,2,3,8,7,4,5,6}

 

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

 

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

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이르버리 사용
    queue = deque([start])
    # 시작 노드를 방문 처리
    visited[start] = True
    
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 노드를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        
        # 꺼낸 노드(v)와 연결된, 아직 방문하지 않은 노드들을 큐에 삽입하고 방문 처리
        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)

# 출력: 1 2 3 8 7 4 5 6

 

 

 

2. 응용: 2차원 배열의 그래프 변환

DFS와 BFS는 2차원 배열 형태의 문제(예: 게임 맵 탐색, 미로 찾기)에서도 사용할 수 있다. 각 좌표를 노드로 간주하고 상하좌우 인접 노드로 그래프를 구성하면 문제를 효과적으로 해결할 수 있다.

 

아래의 코드는 2차원 배열(미로 또는 게임 맵)에서 출발점 (0,0)부터 BFS를 사용하여 이동 가능한 모든 경로를 탐색하는 코드

from collections import deque

# 2차원 배열 그래프 (1은 이동 가능한 길, 0은 벽)
maze = [
    [1, 1, 0],
    [0, 1, 0],
    [1, 1, 1]
]

# BFS로 최단 경로 탐색
def bfs_maze(start_x, start_y):
    # 방향 벡터 (상, 하, 좌, 우)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 시작 좌표를 큐에 삽입
    queue = deque([(start_x, start_y)])
    visited = set()
    visited.add((start_x, start_y))
    
    while queue:
        x, y = queue.popleft()
        print(f'현재 위치: ({x}, {y})')
        
        # 인접한 노드 탐색
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < 3 and 0 <= ny < 3 and maze[nx][ny] == 1 and (nx, ny) not in visited:
                queue.append((nx, ny))
                visited.add((nx, ny))

# BFS 실행 (시작 위치: (0, 0))
bfs_maze(0, 0)

# 출력 결과
# 현재 위치: (0, 0)
# 현재 위치: (0, 1)
# 현재 위치: (1, 1)
# 현재 위치: (2, 1)
# 현재 위치: (2, 0)
# 현재 위치: (2, 2)

 

탐색 순서와 큐의 상태

단계	현재 위치	탐색된 인접 좌표	큐 상태	방문 노드
1	(0,0)	(0,1)	[(0,1)]	{(0,0), (0,1)}
2	(0,1)	(1,1)	[(1,1)]	{(0,0), (0,1), (1,1)}
3	(1,1)	(2,1)	[(2,1)]	{(0,0), (0,1), (1,1), (2,1)}
4	(2,1)	(2,0), (2,2)	[(2,0), (2,2)]	{(0,0), (0,1), (1,1), (2,1), (2,0), (2,2)}
5	(2,0)	없음	[(2,2)]	그대로
6	(2,2)	없음	[]	그대로

 

활용 예시

1. 최단 경로 탐색

• BFS는 가까운 노드부터 탐색하므로, 출발점에서 도착점까지의 최단 경로를 찾는 데 유용하다. 
• ex. 미로 탈출 게임, 게임 맵에서 목표 지점까지 이동

2. 도달 가능 여부 확인

• 특정 좌표에서 시작하여 도달 가능한 모든 좌표를 탐색하고 표시하는 데 사용된다. 
• ex. 게임 캐릭터의 이동 가능한 범위 표시

3. 그래프 탐색

• 2차원 배열을 그래프 형태로 변환하여 문제 해결할 수 있다. 
• ex. 네트워크 탐색, 최단 경로 계산

 

 

 

참고 자료

[1] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈, 한빛미디어)