ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 파이썬 자료구조 알고리즘, BFS -> Queue로 구현
    Python 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] 를 반환한다.

     

Designed by Tistory.