DFS & BFS

👣 개요

그래프 탐색 알고리즘으로
DFS는 Branch를 탐색할 때, 끝까지 탐색 후에 다른 Branch로 넘어가고
BFS는 특정 노드에 인접한 노드를 최우선으로 탐색한다.

DFS

BFS

---

 

👣 알고리즘 절차

👣 DFS - 재귀 함수

1. 시작 노드에서 함수를 호출하고, 방문한 노드에서 다시 함수를 호출합니다.
2. 노드 말단에서 조건문에 의해 더 이상 함수를 호출하지 않을 때까지 반복합니다.

👣 DFS - Stack 

1. 시작 노드를 방문하고, 방문한 노드를 Stack에 넣습니다.
2. Stack에서 가장 최근에 넣은 노드를 꺼내고, 해당 노드의 인접한 미방문 노드를 방문합니다.
   이후, 방문한 노드를 Stack에 넣습니다.
3. Stack이 빌 때까지 2단계를 반복합니다.

👣 BFS - Queue

1. 시작 노드를 방문하고, 방문한 노드를 Queue에 넣습니다.
2. Queue에서 가장 먼저 들어온 노드를 꺼내고, 해당 노드의 인접한 미방문 노드를 방문합니다.
   이후, 방문한 노드를 Queue에 넣습니다.
3. Queue가 비어질 때까지 2단계를 반복합니다.

---

👣 코드 예시

👣 DFS - 재귀 함수

root = {루트 노드}

def recursive_func({선택된 노드}):
    if {노드가 다음 노드로 넘어가기엔 부족한 지}:
        # 다음 노드로의 진행이 부적절하다면 진행을 멈춤.
        return 
    
    {해당 노드에서 수행할 작업}
    
    for {다음 노드} in next_node({선택된 노드}):
        recursive_func({다음 노드})

recursive_func(root)

👣 DFS - Stack

stack = [{루트 노드}]

while stack:
    # 가장 최근에 담겼던 노드를 추출.
    {선택된 노드} = stack.pop()
    
    if {노드가 다음 노드로 넘어가기엔 부족한 지}:
        # 다음 노드로의 진행이 부적절하다면 진행을 멈춤.
        continue
    
    {해당 노드에서 수행할 작업}
    
    for {다음 노드} in next_node({선택된 노드}):
        stack.append({다음 노드})

👣 BFS - Queue

queue = [{루트 노드}]

while queue:
    # 가장 처음에 담겼던 노드를 추출.
    {선택된 노드} = queue.pop(0)
    
    if {노드가 다음 노드로 넘어가기엔 부족한 지}:
        # 다음 노드로의 진행이 부적절하다면 진행을 멈춤.
        continue
    
    {해당 노드에서 수행할 작업}
    
    for {다음 노드} in next_node({선택된 노드}):
        queue.append({다음 노드})

👣 약간 변형된 그래프 탐색 - Heap

from heapq import heappush, heappop

heap = [{루트 노드}]

while heap:
    # 가장 작은 score의 노드를 추출.
    {선택된 노드} = heappop(heap)
    
    if {노드가 다음 노드로 넘어가기엔 부족한 지}:
        # 다음 노드로의 진행이 부적절하다면 진행을 멈춤.
        continue
    
    {해당 노드에서 수행할 작업}
    
    for {다음 노드} in next_node({선택된 노드}):
        heappush(heap, {다음 노드})

👣 노드 선별 작업

위 알고리즘을 그대로 진행하면 완전 탐색이 되기 때문에 어마어마한 연산량을 만들어낼 수도 있다.
때문에 노드의 유망성을 따지고 정답을 찾을 가망성이 전혀 없다면
빠르게 진행을 멈추는 것이 해당 알고리즘을 잘 사용하는 방법이다.
수많은 노하우가 있겠지만 그중 자주 사용하게 되는 조건들을 아래에 적어 기억하고자 한다.

1. 이미 방문한 노드 여부 확인

보통 이미 방문한 노드는 다시 확인할 필요가 없기 때문에 이미 방문한 노드는 더 이상 진행하지 않는다.
이런 경우 Hash를 이용해서 해당 노드가 존재하는지 확인하는 방식으로 풀어낸다.
Ex) 미로찾기 문제, 최소 경로 찾기 문제.

queue = [{루트 노드}]
# hash 자료구조를 가지고 있는 set을 이용함.
visited = set()

while queue:
    # 가장 처음에 담겼던 노드를 추출.
    {선택된 노드} = queue.pop(0)
    
    ###########################
    # 이미 방문한 노드인지 확인.
    if {현재 노드} in visited:
        continue
    visited.add({현재 노드})
    ###########################
    
    {해당 노드에서 수행할 작업}
    
    for {다음 노드} in next_node({선택된 노드}):
        queue.append({다음 노드})

2. 이미 최소값의 이상의 cost를 가지고 있는 노드

보통 이런 문제는 최소값을 찾는 유형일 경우가 많다.
때문에 해당 노드까지 도달하는 cost가 이미 기존에 구해놓았던 값보다 큰 경우라면
당연히 가망성이 없는 Branch이므로 진행하지 않는다.

queue = [{루트 노드}]
# 최소값을 요구하는 문제의 초기값
answer = float('inf')

while queue:
    # 가장 처음에 담겼던 노드를 추출.
    {선택된 노드} = queue.pop(0)
    
    ###########################
    # 최소값을 갱신하는지 확인.
    if answer <= get_answer({선택된 노드}):
        continue
    answer = get_answer({선택된 노드})
    ###########################
    
    {해당 노드에서 수행할 작업}
    
    for {다음 노드} in next_node({선택된 노드}):
        queue.append({다음 노드})