CH 06. 너비 우선 탐색
- 너비 우선 탐색 : 두 항목 간 최단 경로
- 그래프 : 정점과 간선으로 이루어짐
> 바로 이어진 정점은 이웃
> 그래프 종류 : 방향, 무방향
> 키/값 쌍을 넣을 때 순서는 중요하지 않음 (해시테이블은 순서를 가지지 않으므로)
> 최소 실행시간 : O(사람의 수 + 간선의 수)
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
print(graph)
- 큐 (선입선출) <-> 스택 (후입선출)
1) 삽입 (push) : 맨 마지막에 추가
2) 제거 (pop) : 맨 처음 항목 제거
from collections import deque
def person_is_seller(name):
return name[-1] == 'm'
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = []
while search_queue:
person = search_queue.popleft()
if not person in searched:
if person_is_seller(person):
print(person + " is a mango seller!")
return True
else:
search_queue += graph[person]
searched.append(person) ## 확인했다고 체크 필요 ... 무한 반복 여지
return False
search("you")
참고자료
Hello Coding 그림으로 개념을 이해하는 알고리즘
