[알고리즘] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)은 대표적인 그래프 탐색 알고리즘

이를 알기 전에, 스택, 큐, 재귀 함수와 같은 자료구조 기초 개념을 알아야 한다!

스택 (Stack)

데이터를 임시 저장하는 기본 자료 구조 중 하나 (+ 메모리 영역 중 하나)
LIFO 방식 (후입선출)으로 동작하는 자료 구조임
push : 스택에 데이터를 넣는 작업
pop : 스택에서 데이터를 꺼내는 작업
→ 가장 윗부분은 top, 가장 아랫부분은 bottom
선형 구조로 데이터를 저장하며, 데이터를 한쪽 끝에서만 삽입 및 삭제
함수 호출 관리, 깊이 우선 탐색(DFS), 백트래킹, 실행 취소(undo), 웹 페이지 뒤로 가기 등에 사용

⌨️ 예시

파이썬에서는 리스트로 구현할 수 있음

stack = []

stack.append(5) # [5]
stack.append(2) # [5, 2]
stack.pop() # 2가 나옴
stack.append(1) # [5, 1]
stack.append(4) # [5, 1, 4]

큐 (Queue)

데이터를 임시 저장하는 기본 자료 구조 중 하나
FIFO 방식 (선입선출)으로 동작하는 자료 구조임
한쪽에서는 데이터 삽입(rear)만, 반대쪽에서는 데이터 추출(front)만 진행됨 (입구 enQueue와 출구 deQueue 따로 존재함)
프로세스 관리, 대기열, 너비 우선 탐색(BFS), 은행 업무, 우선순위 작업 예약 등에 사용
선형 구조로 데이터를 저장하며, 입구와 출구가 별도로 존재

⌨️ 예시

파이썬에서는 Collections.deque(덱)으로 구현할 수 있음
리스트로 구현할 수 있지만 시간 복잡도 문제 발생할 수 있음
(특정 인덱스의 값을 산출하는 pop 연산 후에 전체적으로 인덱스 재조정하는 과정이 필요하기 때문)

from collections import deque

queue = deque()

queue.append(5) # [5]
queue.append(2) # [5,2]
queue.popleft() # [2] - popleft를 써야함!
queue.append(1) # [2,1]
queue.append(4) # [2,1,4]

print(queue) # 먼저 들어온 순서대로 출력 [2,1,4]

queue.reverse
print(queue) # 나중에 들어온 원소부터 출력 [4,1,2]

재귀 함수

자기 자신을 다시 호출하는 함수
깊이 우선 탐색(DFS)을 실질적으로 구현할 때 자주 사용되는 방법
재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 함
재귀 함수가 반복문보다 유리한 경우도 있고, 불리한 경우도 있음
컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임 (stack overflow)
그래서 스택을 사용해야할 때 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음

---

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

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

• 스택 자료구조(비재귀적) 혹은 재귀 함수 를 이용해 구현

• 시작 노드에서부터 한 경로를 따라 최대한 깊게 탐색한 후, 더 이상 깊이 갈 수 없을 때 다음 경로 탐색함

• 위와 같은 방식으로 탐색하면서 방문한 노드를 스택에 저장하고, 더이상 탐색할 수 없을 때 스택에서 노드를 꺼내어 역순으로 출력함

• 그래프 깊이만큼의 스택 공간(메모리) 필요함

• DFS 활용

  • 그래프 구조를 파악 및 경로 탐색, 연결성 확인하는데 유용하며, 미로 찾기, 퍼즐 해결 등 문제를 해결하는 데 활용됨
    • 순환이 있는 그래프에서도 사용 가능하며, 사이클을 감지할 수 있음
  • 강한 연결 요소(SCC)를 찾는 알고리즘의 기본 구성 요소로 사용됨
  • 위상 정렬(Directed Acyclic Graph, DAG)에서 위상 정렬을 수행하는 데 사용됨

• DFS 작동 원리
  ㄱ. 탐색을 시작할 정점 선택
  ㄴ. 현재 정점을 방문하고 기록 (방문 목록에 추가)
  ㄷ. 인접 정점 중 방문하지 않은 정점으로 이동하고, 다시 또 다른 인접 정점 방문
  ㄹ. 더 이상 갈 곳이 없으면 이전 정점으로 되돌아감
  ㅁ. 이 과정을 반복
  
  

🅰️ 재귀 함수를 이용한 DFS 구현

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set() # 방문한 노드를 저장하는 집합 
    visited.add(start) # 현재 노드 방문 후 visited 집합에 추가
   
    print(start)  # 방문한 노드(정점) 출력

    for neighbor in graph[start]: # 현재 노드 start의 모든 인접 노드(이웃)를 순회함
        if neighbor not in visited: # 이웃 노드가 visited 집합에 없다면, 그 노드를 시작점을 재귀 함수를 호출해 탐색을 계속함
            dfs_recursive(graph, neighbor, visited) 
    return visited # 방문 노드 집합 반환

# 그래프를 인접 리스트로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs_recursive(graph, 'A') # A, B, D, E, F, C (방문한 노드 형태를 집합 형태로 반환)

🅱️ 스택을 활용한 비재귀적 DFS 구현 (인접 리스트 사용)

def dfs_stack(graph, start):
    visited = []  # 방문한 노드를 저장할 리스트
    stack = [start]  # 시작 노드를 스택에 저장
    while stack:
        node = stack.pop()  # 스택에서 노드를 꺼냄
        if node not in visited:
            visited.append(node)  # 방문한 노드를 저장
            # 방문하지 않은 인접 노드를 스택에 추가
            stack.extend([n for n in graph[node] if n not in visited])
    return visited

# 그래프를 인접 리스트로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(dfs_stack(graph, 'A')) # ['A', 'C', 'F', 'E', 'B', 'D']

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

• 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘

• 큐 자료구조 를 이용해 구현

• 시작 노드에서부터 인접한 노드를 먼저 탐색한 후, 더 이상 인접한 노드가 없을 때 다음 단계의 노드를 탐색함

• 위와 같은 방식으로 탐색하면서 방문한 노드를 큐에 저장하고, 순차적으로 큐에서 노드를 꺼내어 탐색함

• 그래프 너비만큼의 큐 공간(메모리) 필요함

• BFS 활용

  • 최단 경로 찾기 : 최단 경로가 동일한 가중치를 가지는 경우에 효과적임 (예-미로 찾기, 최단 경로 찾기, 최소 이동 횟수 게임)
  • 그래프의 모든 정점이 연결되어 있는지 확인하는 데 사용됨 (네트워크 탐색)
  • 레벨 오더 트래버설(Level Order Traversal): 트리나 그래프에서 각 레벨별로 노드를 방문하는 데 사용됨

• BFS 작동 원리
  ㄱ. 탐색을 시작할 정점 선택하고 큐에 추가
  ㄴ. 현재 정점을 방문하고 기록 (방문 목록에 추가)
  ㄷ. 인접 정점들을 모두 큐에 추가 (방문하지 않은 정점만)
  ㄹ. 큐에서 정점 꺼내 방문하고, 해당 정점의 인접 정점들을 다시 큐에 추가
  ㅁ. 큐가 빌 때까지 이 과정을 반복
  
  

🅰️ 큐를 이용한 BFS 구현

from  collections import deque

def bfs(graph, start):
	visited = [] # 방문한 정점을 저장할 리스트
    queue = deque([start]) # 시작 정점을 큐에 추가

    while queue:
    	node = queue.popleft() # 큐에서 정점 꺼냄
        if node not in visited:
        	visited.append(node) # 방문한 정점 저장
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited) # 인접한 정점을 큐에 추가
    return visited

# 그래프를 인접 리스트로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs_recursive(graph, 'A') # A, B, C, D, E, F 

※ 프로그래머스 - 타겟 넘버 (bfs/dfs) 풀어보기 (https://comlini8-8.tistory.com/102)