탐색 알고리즘

• 트리구조
  트리구조는 말그래도 자료의 구조가 트리 형태로 나타난 것을 말한다
  
  위의 사진처럼 원으로 된 노드와 각 노드를 연결해주는 선들로 이루어진 구조이다.

-스택(stack)
스택은 자료구조 중 하나로 입출력을 하는 곳이 하나인 곳에 자료를 하나하나씩 쌓는 구조로 특징은 마지막으로 넣은 자료를 맨 먼저 꺼낸다.

-큐(queue)
큐는 자료를 차례대로 넣는 구조로 스택과 다르게 자료를 입력하고 출력하는 곳이 두 곳으로 나뉘어져 있어 먼저 들어간 자료를 먼저 꺼내게 된다.

깊이우선 탐색(DFS)

위의 트리구조에서 깊이 방향을 우선으로 검색하는 방법으로 일단 하나의 단계를 계속해서 내려다가 더 이상 진행할 방향이 없을 경우에 아직 탐색하지 않는 노드를 다시 찾아서 또 깊이 방향으로 계속 다음 단계의 노드를 찾는 탐색기법

너비우선 탐색(BFS)

너비 방향을 우선으로 검색하는 방법으로 매 단계에서 가능한 경우의 수들을 모두 확인하며 탐색하는 기법으로 일단 다음 단계로 내려가면 더 이상 내려가지 않고 같은 단계의 노드들을 검색하고 현재 단계의 노드들을 검색을 다 한다면 그 다음 단계로 내려가는 것을 반복한다

파이썬으로 DFS / BFS 구현하기

def DFS(start_node, TARGET):
    stack = [start_node, ] #시작노드(root)를 스택에 쌓으면서 

    while True:
             
        if len(stack) == 0: #스택이 비었는지 확인
            print('All node searched.')
            return None
                  
        node = stack.pop() #스택에서 맨 위의 노드를 꺼냄(pop는 마지막 값을 반환하는 함수)
        if node == TARGET: #목표 노드가 있을경우 노드를 반환하고 종료
            print('The target found.')
            return node

        children = expand(node) #node의 자식을 expand 해서 children에 저장
        stack.extend(children) #children을 stack에 쌓기

def BFS(start_node, TARGET):
    queue = [start_node, ] #queue 에 첫 번째 노드 넣으면서 시작
        
    while True:
        if len(queue) == 0: #queue가 비어있는지 확인 
            print('All node searched.')
            return None
            
        node = queue.pop(0) #queue에서 맨 앞의 노드 를 dequeue (0번 인덱스를 pop)
                

        if node == TARGET: #만약 node가 찾고자 하는 target이라면 서치 중단!
            print('The target found.')
            return node

        children = expand(node) #node의 자식을 expand 해서 children에 저장

        queue.extend(children) # children을 stack에 쌓기

출처 : Python｜탐색 알고리즘 뿌시기 (1) DFS, BFS 의 개념과 구현