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

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

• 그래프나 트리에서 한 노드부터 출발하여 최대한 깊게 탐색을 진행한 후, 더 이상 갈 곳이 없으면 이전 단계로 되돌아가서 다른 경로를 탐색하는 방식
• 스택을 이용하여 구현 가능, 재귀적으로도 구현 가능
• 노드의 깊이까지 탐색한 후, 다시 돌아와 다른 경로를 탐색
• 그래프의 모든 노드를 방문하고자 할 때 적합

 

기본 코드 (재귀 방식)

# graph : 탐색할 그래프, start : 탐색 시작 노드, visited : 방문 노드 저장 집합
def dfs(graph, start, visited=None):
	if visited is None:
    	visited = set()
    
    # 현재 노드 방문. 집합에 추가
    visited.add(start)
    print(start, end=' ')
    
    # 현재 노드에 연결된 모든 인접 노드 순회
    for neighbor in graph[start]:
    	# 아직 방문하지 않은 노드라면, dfs 재귀적으로 호출하여 인접 노드 방문
    	if neighbor not in visited:
        	dfs(graph, neighbor, visited)

# 예시 그래프
graph = {
	1: [2, 3, 4],
    2: [5, 6],
    3: [7],
    4: [],
    5: [],
    6: [],
    7: []
}

def(graph, 1)

 

---

 

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

• 그래프나 트리에서 한 노드부터 출발하여 같은 레벨에 있는 모든 노드를 방문한 후, 그 다음 레벨의 노드들을 방문하는 방식.
• 큐를 사용하여 구현 가능
• 최단 경로 찾는 문제에 자주 사용
• 같은 레벨의 노드 모두 방문한 후 다음 레벨로 넘어감

 

기본 코드

from collections import deque

def bfs(graph, start):
	# 방문 노드 기록할 집합 visited 초기화
	visited = set()
    # bfs에서 사용할 큐 초기화, 시작 노드 큐에 추가
    queue = deque([start])
    
    visited.add(start)
    
    # 큐가 비어있지 않은 동안 계속 탐색
    while queue:
    	# 가장 왼쪽의 노드 = 현재 노드로 설정.
    	node = queue.popleft()
        print(node, end=' )
        
        # 현재 노드와 연결된 모든 인접 노드 순회
        for neighbor in graph[node]:
        	visited.add(neighbor)
            queue.append(neighbor)

# 예시 그래프
graph = {
	1: [2, 3, 4],
    2: [5, 6],
    3: [7],
    4: [],
    5: [],
    6: [],
    7: []
}

bfs(graph, 1)

 

---

문제 유형

DFS 사용하는 경우

• 경로의 존재 여부 : 특정 노드에서 목표 노드까지의 경로가 있는지 확인하는 문제
  
  • 중간에 목표 노드 발견시 경로 존재
• 모든 경로 탐색 : 모든 가능한 경로를 탐색해야 하는 경우 (예 : 미로 찾기)
  • 목표 노드 도달 시 경로 저장
• 백트래킹 문제 : 가능한 모든 조합을 시도해야 하는 경우 (예 : 퍼즐 문제, 조합 문제)

BFS 사용하는 경우

• 최단 경로 문제 : 가중치가 전혀 없는 그래프에서 두 노드 간의 최단 경로 찾는 문제
  
  • 먼저 인접한 노드를 탐색하므로, 처음 목표 노드 도달 시 해당 경로가 최단 경로
• 단계별로 진행하는 문제 : 계층적 구조나 넓이 우선으로 탐색해야 하는 문제
• 최소 이동 횟수 문제 : 체스판에서, 말이 최소 몇 번 움직여야 목표 위치에 도달하는지 찾는 문제
  • 각 가능한 이동을 큐에 추가하여 탐색
  • 목표 도달시 이동 횟수 계산, 최소 횟수 기록
  • 큐가 비어있을 때까지 탐색 진행