Python

파이썬 자료구조 알고리즘, BFS -> Queue로 구현

monster route 2024. 7. 23. 01:46

BFS 

저번시간에 배운 DFS는 깊이 우선 탐색으로, 탐색하는 노드를 갈 수 있는 한 최대한 깊이 따라갔다가 더이상 길이 없으면 백해서 다시 노드를 탐색하는 구조였다면 BFS는 Breadth-first search, 너비 우선 탐색이라는 뜻으로, 현재 노드를 시작으로 현재 노드에 인접한 모든 노드들을 먼저 방문한다. 즉, 아래 그래프에서 DFS가 1 > 2 > 5 > 9 > 3 순서로 방문한다면, BFS는 1 > 2 > 3 > 4 > 5 순서로 방문한다.

 

이번에도 코드로 구현해보자.

우선 딕셔너리로 그래프를 작성하고

graph = {
1: [2, 3, 4],
2: [5],
3: [6, 7],
4: [8],
5: [9],
6: [10],
7: [],
8: [],
9: [],
10: [],
}

 

Queue를 사용할거다.

 

일단 BFS는 시작 노드를 지정해야 탐색을 시작할 수 있으니까 start를 인자로 받아 탐색을 시작하는 bfs_queue 함수를 만들면 된다.

 

1. start 노드로 시작해 앞으로 방문하는 노드를 기록할 리스트, visited 와

2. 탐색할 노드를 저장하는 데크 리스트, q 를 만들어준다.

# start를 인자로 받아 탐색을 시작하는 bfs 함수
def bfs_queue(start):
    visited = [start] # 방문 노드를 기록하는 리스트 visited에 start 노드 추가
    q = deque([start]) # 탐색 노드 q에 start 노드 추가

 

 

이제 while 반복문으로, q에 값이 없을 때까지 반복문을 돌려준다.

반복할 일은 q에서 맨 왼쪽 값(q.popleft())를 꺼내 현재 노드로 설정하고 이 노드의 인접 노드들을 확인하여 아직 방문하지 않은 노드들을 visited와 q에 추가하는 거다.

    # 큐가 비어있지 않으면 계속 반복
    while q:
        node = q.popleft() # 큐의 맨 왼쪽 값을 빼서 node에 저장
        # 현재 노드의 인접 노드들을 for문으로 반복
        for adj in graph[node]:
            # 만약 인접 노드가 방문한 노드 리스트에 없으면
            if adj not in visited:
                visited.append(adj) # 방문한 노드 리스트에 추가
                q.append(adj) # 큐에도 추가

    # 큐가 비어있으면 반복문을 끝내고 방문한 노드 리스트 반환
    return visited

print(bfs_queue(1))

 

실행해보면 인접한 노드 순서로 탐색하는 걸 볼 수 있다.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

코드가 어떻게 실행되는지 동작을 설명해보면

 

1. bfs_queue(1) 호출

  • 시작 노드 1 이 탐색 시작

2. 시작

  • visited = [1]
  • q = deq([1])

3. 1차 반복

  • q 에서 꺼낸 node = 1
  • node 1 의 인접 노드: [2, 3, 4]
  • 방문하지 않은 노드: [2, 3, 4]
  • 추가: visited = [1, 2, 3, 4]
  • 추가: q = deq([2, 3, 4])

4. 2차 반복

  • q 에서 꺼낸 node = 2
  • node 2 의 인접 노드: 5
  • 방문하지 않은 노드: [5]
  • 추가: visited = [1, 2, 3, 4, 5]
  • 추가: q = deq([3, 4, 5])

5. 3차 반복

  • q 에서 꺼낸 node = 3
  • node 3 의 인접 노드: [6, 7]
  • 방문하지 않은 노드: [6, 7]
  • 추가: visited = [1, 2, 3, 4, 5, 6, 7]
  • 추가: q = deq([4, 5, 6, 7])

6. 4차 반복

  • q 에서 꺼낸 node = 4
  • node 4 의 인접 노드: [8]
  • 방문하지 않은 노드: [8]
  • 추가: visited = [1, 2, 3, 4, 5, 6, 7, 8]
  • 추가: q = deq([5, 6, 7, 8])

7. 5차 반복

  • q 에서 꺼낸 node = 5
  • node 5 의 인접 노드: [9]
  • 방문하지 않은 노드: [9]
  • 추가: visited = [1, 2, 3, 4, 5, 6, 7, 8, 9]
  • 추가: q = ([6, 7, 8, 9])

8.  6차 반복

  • q 에서 꺼낸 node = 6
  • node 6 의 인접 노드: [10]
  • 방문하지 않은 노드: [10]
  • 추가: visited = [1, 2, 3, 4, ,5, 6, 7, 8, 9, 10]
  • 추가: q = deq([7, 8, 9, 10])

9.  7차 반복

  • q 에서 꺼낸 node = 7
  • node 7 의 인접 노드: X
  • 추가: visited = [1, 2, 3, 4, ,5, 6, 7, 8, 9, 10]
  • 추가: q = deq([8, 9, 10])

10.  8차 반복

  • q 에서 꺼낸 node = 8
  • node 8 의 인접 노드: X
  • 추가: visited = [1, 2, 3, 4, ,5, 6, 7, 8, 9, 10]
  • 추가: q = deq([9, 10])

11.  9차 반복

  • q 에서 꺼낸 node = 9
  • node 9 의 인접 노드: X
  • 추가: visited = [1, 2, 3, 4, ,5, 6, 7, 8, 9, 10]
  • 추가: q = deq([10])

12. 10차 반복

  • q 에서 꺼낸 node = 10
  • node 10 의 인접 노드: 없음
  • 인접노드가 없으므로 방문하지 않은 노드: 없음
  • 추가된 visited 리스트: x 
  • q = deq([])

13. 반복 종료

  • q 가 빈 값이 되었으므로 더이상 반복하지 않고 visited = [1, 2, 3, 4, ,5, 6, 7, 8, 9, 10] 를 반환한다.