너비 우선 탐색 (BFS)

동빈나 실전 알고리즘 강좌 - 16강 BFS

너비 우선 탐색 (BFS) 알고리즘 개념

너비 우선 탐색(Breadth First Search, BFS)는 탐색을 할 때 너비를 우선적으로 선택하여 탐색을 수행하는 탐색 알고리즘이다.

• 맹목적인 탐색을 하고자 할 때 사용할 수 있는 탐색 기법이다.

너비 우선 탐색은 최단 경로를 찾아준다는 점에서 최단 길이의 보장할 때 많이 사용한다.
이때, 사용되는 자료구조는 큐(Queue) 이다.

BFS는 맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작한다.
또한, 시작 노드를 방문 한 점을 기억해야한다. (방문 처리는 빨간색으로 색칠)

이제, BFS는 다음과 같은 간단한 알고리즘에 따라 작동한다.

1. 큐에서 하나의 노드를 꺼낸다.
2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

위 1번과 2번을 계속해서 반복한다.

쭉 방문하게 되면 아래의 그림과 같이 모두 다 방문하게 된다.

이제부터는 남은 노드들을 모두 큐에서 꺼내주기만 하면 된다.

따라서, 방문 경로는 1→2→3→4→5→6→7 이다.

너비 우선 탐색 (BFS) 알고리즘 코드

해당 개념을 python 코드로 작성해보자❗

동빈나 실전 알고리즘 강좌에서는 C++로 되어있기에 python으로 변경하여 코드를 작성하였습니다.

number = 7
check = [False for _ in range(8)] # 방문을 저장할 리스트
arr = [[] for _ in range(8)] # 원소 리스트 [=> 1부터 시작할 수 있도록 8로 만들기]

def bfs(start):
    queue = []
    queue.append(start)
    check[start] = True

    while len(queue) > 0:
        x = queue[0]
        print(x, end = ' ')
        queue = queue[1:] # 앞에 원소 제거

        for i in range(len(arr[x])):
            y = arr[x][i]
            if check[y] is False:
                queue.append(y)
                check[y] = True

# 1과 2를 연결 한다.
arr[1].append(2)
arr[2].append(1)

# 1과 3을 연결한다.
arr[1].append(3)
arr[3].append(1)

# 2과 3을 연결한다.
arr[2].append(3)
arr[3].append(2)

# 2과 4을 연결 한다.
arr[2].append(4)
arr[4].append(2)

# 2과 5를 연결한다.
arr[2].append(5)
arr[5].append(2)

# 3과 6을 연결한다.
arr[3].append(6)
arr[6].append(3)

# 3과 7을 연결한다.
arr[3].append(7)
arr[7].append(3)

# 4와 5를 연결한다.
arr[4].append(5)
arr[5].append(4)

# 6과 7을 연결한다.
arr[6].append(7)
arr[7].append(6)

# BFS를 수행한다.
bfs(1)

이러한 BFS는 너비를 우선으로 하여 탐색한다는 특성이 중요한 것이며, 이를 이용해 다른 알고리즘에 적용한다는 것이 핵심이다.

[References]
https://blog.naver.com/ndb796/221230944971
https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16