BFS 이론 정리

BFS 란?

BFS와 DFS의 차이는 어떤 자료구조를 사용하느냐로 너비 우선 탐색인지, 깊이 우선 탐색인지 갈리게 된다.

BFS는 Queue 자료구조를 사용하여 들어온 순서대로 나가는 FIFO 원칙에 따라 너비 우선 탐색이 수행된다.

코드 정리

V, E = map(int, input().split())  # Vertex, Edge 갯수

adj_matrix = [[0] * (V + 1) for _ in range(V + 1)]  # 인접행렬 기본틀

for _ in range(E):  # 간선 갯수만큼 돌면서 연결 정보를 받음
    start, end = map(int, input().split())  # 시작점과 끝점
    adj_matrix[start][end] = 1
    adj_matrix[end][start] = 1  # 양방향 그래프니까!!

Q = [1]  # 맨처음 시작점은 1번 포도알
visited = []  # 궤적 기록용

while Q:  # 큐가 빌때까지 돌아라!
    current = Q.pop(0)  # 우선 큐에서 현재 위치 "앞에서부터" 뽑고,
    if current not in visited:  # 방문하지 않은 곳이라면,
        visited.append(current)  # 방문했다고 체크해줌

    for destination in range(V+1):  # current 입장에서 어디로 갈 수 있는지 모조리 체크
        if adj_matrix[current][destination] and destination not in visited:  # 갈수있고 + 방문 안했으면!
            Q.append(destination) # 다음 갈 곳으로 큐에 저장

print('이동경로:', *visited)

# 이동경로: 1 2 3 4 5 7 6

파이썬은 배열에 데이터를 담고, pop(0)로 큐를 구현할 수 있다.

또는 앞뒤로 데이터를 삽입하고, 삭제할 수 있는 아래와 같은 deque를 사용하여 구현할 수 있다. 

from collections import deque