알고리즘 유형공부 - BFS와 DFS

DFS와 BFS

1. DFS

1. 개요

깊이 우선 탐색(Depth First Search, DFS)은 그래프 탐색 알고리즘으로, 한 노드를 선택한 후 가능한 깊이까지 탐색한 후 돌아와 다른 경로를 탐색합니다.

2. 알고리즘의 원리

1. 시작 노드에서 출발합니다.
2. 방문하지 않은 인접 노드가 있으면 그 노드로 이동하고 방문 처리를 합니다.
3. 더 이상 방문할 수 있는 노드가 없으면 이전 노드로 돌아갑니다.
4. 모든 노드를 방문할 때까지 이 과정을 반복합니다.

주로 스택을 사용하며, 재귀 호출로 구현할 수 있습니다.

3. 시간복잡도 및 공간복잡도

• 시간복잡도 `: O(V + E) (V: 노드 수, E: 간선 수)
• 공간복잡도 `: O(V)

4. 예시 코드

# DFS 예시 코드 (재귀 버전)
def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 예제 그래프 (인접 리스트)
graph = [
    [],        # 0번 노드 (사용하지 않음)
    [2, 3, 4], # 1번 노드와 연결된 노드들
    [1, 5],    # 2번 노드와 연결된 노드들
    [1, 6],    # 3번 노드와 연결된 노드들
    [1],       # 4번 노드와 연결된 노드들
    [2],       # 5번 노드와 연결된 노드들
    [3]        # 6번 노드와 연결된 노드들
]

visited = [False] * 7

# DFS 실행
dfs(graph, 1, visited)

5. 추천 문제

• 백준 1260번: DFS와 BFS
• 프로그래머스: 타겟 넘버

2. BFS

1. 개요

너비 우선 탐색(Breadth First Search, BFS)은 그래프 탐색 알고리즘으로, 시작 노드에서 가까운 노드부터 탐색하는 방법입니다.

2. 알고리즘의 원리

1. 시작 노드에서 출발합니다.
2. 방문한 노드를 큐(Queue)에 삽입하고 방문 처리를 합니다.
3. 큐에서 노드를 꺼내어 인접 노드를 확인하고, 방문하지 않은 노드를 다시 큐에 삽입합니다.
4. 큐가 빌 때까지 이 과정을 반복합니다.

3. 시간복잡도 및 공간복잡도

• 시간복잡도: O(V + E) (V: 노드 수, E: 간선 수)
• 공간복잡도: O(V)

4. 예시 코드

from collections import deque

# BFS 예시 코드
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 예제 그래프 (인접 리스트)
graph = [
    [],        # 0번 노드 (사용하지 않음)
    [2, 3, 4], # 1번 노드와 연결된 노드들
    [1, 5],    # 2번 노드와 연결된 노드들
    [1, 6],    # 3번 노드와 연결된 노드들
    [1],       # 4번 노드와 연결된 노드들
    [2],       # 5번 노드와 연결된 노드들
    [3]        # 6번 노드와 연결된 노드들
]

visited = [False] * 7

# BFS 실행
bfs(graph, 1, visited)

5. 추천 문제

• 백준 2178번: 미로 탐색
• 프로그래머스: 게임 맵 최단거리

3. DFS와 BFS 비교

1. 장단점 및 차이점점 비교

특징	DFS	BFS
장점	- 구현이 간단 (재귀 사용 가능)	- 최단 경로를 찾을 때 유리
	- 메모리 사용량이 적을 수 있음
단점	- 최단 경로 보장 X	- 큐 사용으로 메모리 사용량이 많을 수 있음
방식의 차이점	한 점에서 시작하여 갈 한 방향으로만 이동한다고 생각하면 이해하기 편함.	한 점에서 시작해서 한칸 이동한 점들을 구하고, 그 다음에서 한칸 이동한 점들을 구하고 이런 방식이라고 이해하자.

2. 언제 무엇을 선택할까?

• DFS: 경로를 탐색하며 가능한 모든 경우를 확인해야 할 때 (예: 미로 찾기, 백트래킹).
• BFS: 최단 경로를 찾을 때 (예: 최단 거리 문제, 네트워크 탐색).

3. 유형 및 응용

• DFS 응용: 백트래킹, 위상 정렬, 사이클 검사
• BFS 응용: 최단 경로 문제, 네트워크 탐색, 레벨별 탐색