[Python 기본] 탐색 알고리즘(DFS / BFS) 2

deque

- 파이썬 리스트의 한계로 인해 Queue를 운영하다 보면 속도의 이슈가 생김

- 이런 이슈를 해결하기 위해 사용하는 패키지

from collections import deque

a_dq = deque([1,2,3])
a_dq
# deque([1,2,3])

# 원소 추가
a_dq.append(4)
a_dq
# deque([1,2,3,4])

# 원소 빼기(pop)
a_dq.pop()
# 4

a_dq.popleft() # Queue = pop(0) 대신 사용
# 1

 

 

탐색 알고리즘 코드화

graph = [
    [], # 가상의 0번 도시
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

 

[DFS]

need_visit = [] # 가야할 노드의 목록
visited = [] # 방문한 노드의 목록
start = 1 # 시작 지점

need_visit.append(start) # 가야할 노드의 목록에 시작 지점 추가

while need_visit: # 출발 -> 가야할 노드의 목록이 없어질 때까지!
  node = need_visit.pop() # DFS -> Stack 방식으로 노드 방문
  if node not in visited: # 이미 방문한 노드인지 확인 -> 방문하지 않은 노드만!
    visited.append(node)
    need_visit.extend(graph[node]) # 연결된 노드의 목록을 가야할 노드의 목록에 추가
    							   # extend에 주의!

print(visited)
# [1, 8, 7, 6, 2, 3, 5, 4]

 

[BFS]

- DFS와의 차이점은 deque를 쓴다는 것과 popleft()(=pop(0))을 쓴다는 것이다.

from collections import deque

need_visit = deque([]) # 가야할 노드의 목록 -> deque
visited = deque([]) # 방문한 노드의 목록 -> deque
start = 1 # 시작 지점

need_visit.append(start) # 가야할 노드의 목록에 시작 지점 추가

while need_visit: # 출발 -> 가야할 노드의 목록이 없어질 때까지!
  node = need_visit.popleft() # BFS -> Queue 방식으로 노드 방문
  if node not in visited: # 이미 방문한 노드인지 확인 -> 방문하지 않은 노드만!
    visited.append(node)
    need_visit.extend(graph[node]) # 연결된 노드의 목록을 가야할 노드의 목록에 추가

print(list(visited))
# [1, 2, 3, 8, 7, 4, 5, 6]