알고리즘 - DFS, BFS

참고한 블로그 : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

BFS (너비 우선 탐색)

사진 출처 : https://velog.io/@gusdh2/DFS-vs-BFS-깊이우선탐색-vs-너비우선탐색

개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

즉 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택함

보통 deque를 활용함. 그리고 DFS와 마찬가지로 방문 여부가 거의 필수다. 그리고 재귀적으로 동작하는게 아니라 큐에 값이 빌 때까지 while문 도는 구조. FIFO(선입 선출) 원칙으로 탐색함.

자료구조

큐 (Queue) 사용

선입선출(FIFO, First-In-First-Out) 방식으로, 먼저 들어온 노드를 먼저 처리.

Python에서는 collections.deque를 이용해 큐를 구현하는 것이 효율적.

시간 및 공간 복잡도

시간 복잡도: O(V + E)

V: 정점의 개수 (Nodes)

E: 간선의 개수 (Edges)

모든 정점을 한 번씩 방문하고, 간선도 한 번씩 탐색하기 때문에 O(V + E)가 됩니다.

공간 복잡도: O(V)

큐와 방문 리스트를 사용하므로, 정점의 개수에 비례하는 메모리가 필요.

from collections import deque

def bfs(graph, start):
    # 방문 여부를 체크하는 리스트
    visited = [False] * len(graph)
    
    # 시작 노드를 큐에 추가하고 방문 처리
    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, 8],   # 1번 노드와 연결된 노드들
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# BFS 실행
bfs(graph, 1)
# 출력: 1 2 3 8 7 4 5 6

BFS 활용 예시

최단 경로 문제

• 미로 탐색, 지형에서 특정 지점까지의 최단 거리 찾기 등에서 사용.

네트워크 탐색

• SNS에서 친구 추천, 웹 크롤러 등에서 사용.

레벨 탐색

• 트리에서 각 레벨별로 노드를 방문하거나 레벨 단위로 그룹화할 때 유용.

BFS의 주의 사항

• 큐를 사용하기 때문에, 노드의 수가 많거나 깊이가 깊은 그래프에서는 메모리 사용량이 급증할 수 있다.
• 모든 노드를 방문하기 때문에 가중치가 있는 그래프에서 최단 경로를 찾는 경우에는 다익스트라 알고리즘이 더 효율적일 수 있음.

DFS (깊이 우선 탐색)

사진 출처 : https://velog.io/@gusdh2/DFS-vs-BFS-깊이우선탐색-vs-너비우선탐색

개념

참고한 블로그 : https://yunyoung1819.tistory.com/86#google_vignette

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함

즉 넓게(wide) 탐색하기 전에 깊게(deep) 탐색함

모든 노드를 방문하고자 하는 경우에 이 방법을 선택함

깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함

검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다

방문 유무 필수로 확인해야 함. 그렇지 않으면 무한 루프에 빠질 수 있다.

자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다.

자료구조

스택 (Stack) or 재귀 함수를 사용.

스택을 명시적으로 사용할 수도 있지만, Python에서는 재귀 호출을 통해 스택을 간접적으로 사용할 수 있습니다.

시간 및 공간 복잡도

시간 복잡도 : O(V + E)

모든 정점과 간선을 한 번씩 방문하기 때문이다.

공간 복잡도 : O(V)

재귀 호출 스택에 의한 공간 사용이 발생하며, 최대 깊이는 그래프의 깊이와 비례.

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 = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * len(graph)

# DFS 실행
dfs(graph, 1)
# 출력: 1 2 7 6 8 3 4 5

DFS 활용 예시

백트래킹 문제

퍼즐 풀이 (예: N-Queens 문제), 조합 탐색 (예: 순열 및 조합 생성)

경로 찾기

모든 가능한 경로를 탐색하고 싶은 경우 (예: 모든 경로 찾기 문제).

사이클 검출

그래프에서 사이클이 존재하는지 확인할 때 DFS가 유용.

DFS의 주의 사항

• 스택 오버플로우 : 그래프의 깊이가 깊거나 순환 구조가 있는 경우 재귀 깊이 제한을 초과할 수 있다.
• Python에서는 sys.setrecursionlimit()을 사용해 재귀 깊이를 조정할 수 있지만, 무리하게 늘리는 것은 권장되지 않음.

BFS와 DFS 비교

특성	BFS	DFS
탐색 순서	너비 우선 (Level-wise)	깊이 우선 (Depth-wise)
자료구조	큐 (Queue)	스택 (Stack) / 재귀 호출
최단 경로 보장	예 (가중치 없는 그래프에서)	보장하지 않음
경로 탐색	전체 노드 탐색 후 종료	깊이 우선 탐색 후 백트래킹
메모리 사용	많은 메모리 사용 가능	재귀 깊이 제한에 주의
활용 예제	최단 경로 문제, 네트워크 탐색	백트래킹 문제, 순열 및 조합 문제