BFS(너비 우선 탐색)

BFS(Breadth First Search, 너비우선 탐색)은 그래프를 방문하거나 탐색하는 방법 중 하나이다. BFS를 이용하여 최단거리, 최소비용과 같이 최솟값과 관련된 문제를 해결할 수 있는데, 이때 그래프의 가중치(시간, 비용, 거리 등)가 1이어야만 한다. DFS는 그래프의 최대 경로(최대 깊이)가 예측할 수 있는 유한한 범위여야만 사용할 수 있지만, BFS는 모든 경로에 대한 동시 탐색이 가능하며 최대 경로를 몰라도 사용할 수 있다. 

 

from collections import deque

def bfs(start):
    visited[start] = True
    queue.append(start)
    while queue:
        x=queue.popleft()
        for i in range(len(adj[x])):
            y=adj[x][i]
            if not visited[y]:
                visited[y] = True
                queue.append(y)

#N:정점개수 M:간선개수
N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
queue = deque()
start_node = input('검색을 시작할 노드를 입력하세요 : ')

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)

bfs(start_node)

백준 11724번 코드 중 일부를 가져와 수정했다. 해당 코드는 정점, 간선의 개수를 입력받고 사용자에게 직접 어떤 정점이 연결되어 있는지 입력받는다.

 

BFS의 경우 큐를 사용하는 경우가 대부분이다. 방문했던 노드를 체크해야 살펴볼 노드를 큐에 넣을 때 중복이 발생하지 않기 때문이다.

 

python에서는 큐를 list 타입으로 사용하는 경우가 많은데, 살펴본 노드를 제거할 때, list.pop() 함수를 사용하는 경우 시간 복잡도가 O(N)이라 시간 복잡도 면으로 매우 비효율적이다.

 

따라서 collections 라이브러리의 deque을 사용하여 시간을 절약하는 편이 좋다. deque는 양 끝에서 접근이 가능하며, append(), extend(), pop(), popleft() 등의 함수를 통해 자료를 넣고 뺄 수 있다.