[Python] DFS, BFS 알고리즘

 

# 전역 변수
# 트리를 딕셔너리 형태로 표현
# Key: 노드 / Value : 하위 노드 list
graph = {
    1:[2,3,4],
    2:[5],
    3:[5],
    4:[],
    5:[6,7],
    6:[],
    7:[3]
}

---

DFS (깊이 우선 탐색, Depth First Search)

• 루트 노드(최상위)부터 리프 노드(최하위)까지 탐색한 후, 다시 올라와서 내려가는 방식
• 스택(Stack)을 활용할 수 있음
• 재귀(Recursion) 함수를 활용할 수 있음

# 재귀 함수 이용한 DFS
# Input : 최상위 노드 값
def recursion_dfs(node, discovered=[]):
    discovered.append(node) # 탐색한 노드에 추가
    for x in graph[node]: # 해당 노드 하위의 모든 노드
        if x not in discovered: # 탐색한 적 없으면
            discovered = recursion_dfs(x, discovered) # 재귀 함수 실행
    return discovered #최종 탐색 결과

# Stack 이용한 DFS
# Input : 최상위 노드 값
def stack_dfs(node):
    discovered = []
    stack = [node] #최초 루트 노드
    while stack: # 스택이 빌 때 까지
        v = stack.pop() # 스택에서 꺼내옴
        if v not in discovered: # 탐색한 적이 없으면
            discovered.append(v) # 탐색한 노드에 추가
            for w in graph[v]: # 해당 노드의 모든 하위 노드
                stack.append(w) # 스택에 추가
    return discovered #최종 탐색 결과

 

---

BFS (너비 우선 탐색, Breadth First Search)

• 루트 노드(최상위)부터 한 단계씩 내려가면서 탐색하는 방식
• 큐(Queue)을 활용할 수 있음
• 재귀(Recursion) 함수를 활용할 수 없음

# Queue를 이용한 BFS
# Input : 루트 노드 값
def bfs(root):
    discovered = [root] # 탐색한 노드에 루트 노드 추가
    queue = [root] # 큐에 루트 노드 추가
    while queue: # 큐가 빌 때 까지 반복
        x = queue.pop(0) # 큐에서 꺼내옴
        
        for node in graph[x]: # 해당 노드의 모든 하위 노드
            if node not in discovered: # 탐색한 적이 없으면
                discovered.append(node) # 탐색한 노드에 추가
                queue.append(node) # 큐에 추가

    return discovered #탐색 결과

 

---

본 포스팅은 「파이썬 알고리즘 인터뷰」를 참고했습니다.