-
파이썬 자료구조 알고리즘, 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] 를 반환한다.
'Python' 카테고리의 다른 글
파이썬, 자료구조 알고리즘, array & list (0) 2024.07.25 파이썬, class, Exception, 시간복잡도 공간복잡도, Big-O Notation (2) 2024.07.24 파이썬 자료구조 알고리즘, DFS -> 재귀함수로 구현 (0) 2024.07.21 파이썬 자료구조 알고리즘, 코딩테스트 문제, n번째 피보나치 수 구하기 (2) 2024.07.19 파이썬, 자료구조 알고리즘, is_pelindrome code (0) 2024.07.19