[Algorithm] BFS 이론 + 구현

❗BFS

너비 우선 탐색이라는 그래프 탐색 기법으로 시작 노드에서 연결된 자식 노드를 모두 탐색 후 다시 자식 노드가 부모 노드가 되어 이 부모 노드의 자식 노드를 넓게 탐색하는 방식이다

BFS를 구현하는 방식으론 큐를 이용한다.

 

❗동작 방식

위와 같은 그래프가 있고, 1번 노드에서 시작하여 탐색하고자 한다.

손으로 BFS를 풀 때는 1 -> 3 -> 2까지 탐색 후 다음 방문 노드는 3번 노드의 자식 노드인 6번과 4번이 된다.

1 -> 3 -> 2 -> 6 -> 4 다음엔 2번 노드의 자식 노드인 5번을 방문하고

1 -> 3 -> 2 -> 6 -> 4 -> 5 순서로 그래프 탐색을 완료할 수 있다.

 

❗파이썬 구현

위의 케이스를 파이썬 코드로 구현한 것이다.

graph = [[],[3,2],[3,1,4,5],[6,4,2,1],[3,2],[2],[3]]
visited = [0] * (7)

bfs(graph, 1, visited)

먼저, graph를 선언 시 2차원 배열로 선언하게 되고, 각 요소의 인덱스가 그래프의 노드 번호가 된다.

해당 인덱스에 있는 배열은 각각의 노드와 연결되어 있는 다른 노드의 집합이다!

그 다음 visited를 선언하여 노드를 거슬러 올 때, 방문 여부를 판단할 수 있도록 한다.

bfs 함수의 파라미터로 그래프, 방문 노드 번호, 방문 배열을 넣어준다.

 

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = 1

    while queue:
        v = queue.popleft()
        print(v, end=" ")

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = 1

파이썬에서 queue를 사용하기 위해 deque로 queue를 선언해준다. 

함수 구현부를 보면 start로 방문한 노드 번호를 받았기 때문에 시작점을 포함하여 queue를 만들어 주고,

visited 배열에서 방문 처리를 해준다.

queue가 비어있지 않은 동안 탐색을 반복할 것이기 때문에 while문 안에 구현하고, queue에서 맨 앞에 있는 노드를 꺼내서 v에 할당해준다.

graph[v]는 방문한 노드에 연결된 노드의 집합이고, 이를 i 변수로 하나씩 꺼내오게 된다.

i를 방문했는지 판단하고, 방문하지 않았을 경우만 i를 queue의 맨 오른쪽에 삽입하게 된다.

그리고 i를 방문 처리해준다. 위의 과정을 반복하고 queue가 비었을 때 bfs 함수가 종료된다.

 

아래는 코드 전문입니다.

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = 1

    while queue:
        v = queue.popleft()
        print(v, end=" ")

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = 1


graph = [[],[3,2],[3,1,4,5],[6,4,2,1],[3,2],[2],[3]]
visited = [0] * (7)

bfs(graph, 1, visited)

 

❗참고 문제

https://www.acmicpc.net/problem/1260

https://radiant515.tistory.com/493

[Baekjoon] 백준 1260 DFS와 BFS Python