(Algorithm) DFS와 BFS

요약

• DFS는 시작 노드에서 자식 노드를 깊이 우선으로 탐색하며 주로 스택이나 재귀 함수를 통해 구현하는 방식입니다.
• 이 방식은 메모리 효율이 좋고 그래프 순환 감지에 유리하지만 최단 경로 탐색에는 적합하지 않으며 무한 루프의 위험이 있습니다.
• BFS는 인접한 노드들을 먼저 탐색하는 너비 우선 방식으로 선입선출 구조인 큐를 활용하여 구현합니다.
• 가중치가 없는 그래프에서 최단 경로를 찾는 데 탁월하지만 노드 수가 많거나 분기 계수가 클수록 메모리 소모가 심합니다.
• 따라서 모든 노드를 방문하거나 깊은 탐색이 필요하면 DFS를, 최단 거리를 구해야 한다면 BFS를 선택하는 것이 중요합니다.

---

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

1. 1 개념

시작 노드에서 자식 노드들을 깊이를 우선으로 순서대로 탐색하는 알고리즘

깊이 우선으로 모든 경우의 수를 탐색하는 완전 탐색 알고리즘에 속하지만, 항상 그렇지는 않다. Stack을 활용한 반복문에 쓰이거나, 재귀문을 통해 구현된다.

1.2 탐색과정

DFS의 기본 탐색과정은 특정 노드에서 시작하여 역추적(Backtracking) 하기 전에 가능한 자식 노드들을 멀리 탐색한다.

1. 특정 노드를 방문했으면, 방문했다고 표시
2. 해당 노드의 자식 노드를 탐색
3. 더이상 자식 노드가 없으면 역추적
4. 방문한 적이 없는 노드를 탐색
5. 모든 노드를 방문할 때 까지 위 프로세스 반복

1.3 특징

장점

1. DFS는 현재 순회 중인 노드만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간 덜 차지한다.
2. 특정 노드 또는 모든 노드를 탐색하는 것이 목적이라면 유용하다.
3. 그래프 순환 감지가 가능하다.

단점

1. 그래프 구조가 순환인 경우, 무한 루프에 빠질 수 있다.
2. 두 노드 사이의 최단 경로를 찾으려는 경우 적합하지 않은 알고리즘

1.4 구현 방법

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

반복 구현 (stack)

참고( 데이터 스택 구조란?)

• 데이터가 차곡차곡 쌓아 올리는 형태로, 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조
• push : 새로운 데이터를 가장 맨 위(top)위치에 삽입
• pop: 맨 위(top) 데이터를 제거

스택 데이터 구조를 사용하여 반복 구현을 통해 방문할 노드를 추적한다.

1. 임의의 노드를 시작점으로 방문한 것으로 표시하고 스택에 push
2. top에 위치한 노드를 가져온다.
3. 방문하지 않은 모든 인접 노드를 방문한 후 방문한 표시를 스택에 push
4. 스택이 비워질 때 까지 반복

def stack_dfs(root):
    visited = []
    stack = [root]
    
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for w in graph[v]:
                stack.append(w)
    
    return visited
 
print(stack_dfs(1)) #[1,4,3,5,7,6,2]

재귀 구현

재귀 함수를 사용하여 그래프의 모든 노드를 방문한다. 현재 노드와 방문한 집합을 입력값으로 사용하고 아직 방문하지 않은 모든 인접한 노드에 DFS를 적용한다.

위 방법은 모든 노드를 방문하는 것이 목적일 때 유용하다.

def recursive_dfs(root, visited=[]): 
	visited.append(root) 
	
	for w in graph[root]: 
		if w not in visited: 
			visited = recursive_dfs(w, visited) 
	return visited
 
print(recursive_dfs(1, [])) #[1,2,]

비교

두 방법 모두 시간 및 공간 복잡도는 동일하다.

일반적으로 반복 구현(Stack)은 호출 스택을 사용하지 않기 때문에 공간 측면에서 더 효율적 재귀 구현은 반복 구현보다 간단하고 간결하여 가독성이 좋다. 그러나 그래프 크기가 크거나 순환 구조인 경우 스택 오버플로 발생한다.

---

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

2.1 개념

시작 노드에서 자식 노드들을 너비를 우선으로 순서대로 탐색하는 알고리즘

BFS는 완전 탐색 알고리즘에 속하며, 가중치가 없는 그래프에서 동일한 거리에 있는 모든 노드를 탐색한다. 이후 거리의 노드를 탐색하기 시작하는 방식이다.

따라서, 가중치가 없는 그래프에서 최단거리를 구하는 문제에 활용된다. Queue를 활용해 다음 방문할 노드를 추적하거나, While 반복문을 통한 문제를 해결한다.

2.2 탐색 과정

참고( 큐(Queue)의 개념)

• 선입선출(FIFO, First In First Out)로 먼저 들어온 데이터가 먼저 나가는 방식의 선형 자료구조
• front에서 데이터를 삭제(dequeue)한다.
• rear에서 데이터를 삽입(enqueue)한다.

1. 시작 노드에서 시작하고 대기열(Queue)에 삽입한다.
2. 대기열에서 노드를 제거하고 검사(poll = dequeue)한다.
3. 검사한 노드가 목표 노드라면 검색 완료
4. 그렇지 않은 경우, 검사한 노드에 속한 자식 노드 중 방문하지 않은 자식 노드를 큐에 넣는다(offer = enqueue)
5. 대기열이 비어 있거나 목표 노드를 찾을 때까지 위 단계 반복한다.

2.3 특징

장점

1. 간단하고 이해하기 쉽다.
2. 연결된 구성 요소에서 모든 노드를 찾는데 사용 가능하다.

단점

1. 많은 메모리가 필요하므로 그래프가 큰 경우 적합하지 않다.
2. 그래프 순회 시, 가중치 고려하지 않기 때문에 가중치 링크가 있는 그래프에는 적합하지 않다.
3. 다음 깊이로 이동하기 전에 노드의 모든 하위 항목을 탐색하기 때문에 분기 계수가 큰 그래프에는 비효율적이다.(분기 계수란, 각 노드가 평균적으로 가지고 있는 자식 노드의 개수)
4. 다음 깊이로 이동하기 전에 현재 깊이의 모든 노드를 방문하기 때문에 노드 수가 많은 그래프에는 비효율적이다.
5. 목표 노드가 시작 노드에서 멀리 떨어져 있으면 다음 깊이로 이동하기 전에 주어진 깊이의 모든 노드를 탐색하기 때문에 비효율적이다.

비교

• BFS는 메모리 사용량이 많고, 노드 수가 많은 그래프에는 적합하지 않다.
• 또한, 가중치 링크가 존재하는 그래프의 경우 제대로 작동하지 않을 수 있다.

2.4 구현 방법

주로 그래프가 주어졌을 때, 경로를 찍어주는 예제에 활용된다. 0번 시작 노드를 Queue에 넣고, while 반복문을 통해 Queue가 비워질 때 까지 탐색한다.

또한, 중복이 발생할 경우를 대비하여 boolean 배열 visited를 선언하여 방문처리를 구현한다.

# 예시 그래프
graph = { 
	1 : [2,3,4], 
	2 : [5], 
	3 : [5], 
	4 : [], 
	5 : [6,7], 
	6 : [], 
	7 : [3]K
}
 
from collections import deque 
 
def BFS(root): 
	visited = [root] # 현재 노드 방문 처리 
	queue = deque([root]) 
	
	while queue: 
		v = queue.popleft() # 큐에서 원소 꺼내기 
		for w in graph[v]: 
			if w not in visited: 
				visited.append(w) 
				queue.append(w) 
	return visited
 
print(BFS(1)) #[1,2,3,4,5,6,7]

---

참고사이트

• DFS 깊이 우선 탐색 알고리즘이란?
• BFS 너비 우선 탐색 알고리즘이란?
• BFS/DFS 차이
• DFS & BFS
• 코딩테스트 대비 DFS, BFS 정리