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

DFS(깊이 우선 탐색)

필수 개념

1. 스택: DFS는 일반적으로 스택 자료 구조를 사용하여 구현되며, 이는 재귀 호출을 통해 간접적으로 구현될 수도 있습니다.
2. 재귀: DFS는 재귀적으로 호출하여 각 노드를 방문할 수 있습니다.
3. 백트래킹: DFS는 탐색 중에 가능한 모든 경로를 탐색하고, 더 이상 진행할 수 없을 때 이전 단계로 돌아가는 방식입니다.

DFS의 기본 로직

1. 초기화:
   • 시작 노드를 지정하고, 방문 여부를 추적할 자료 구조를 초기화합니다. 보통 집합(set)이나 배열을 사용합니다.
2. 탐색 시작:
   • 시작 노드를 스택에 추가하거나, 재귀 함수를 호출합니다.
3. 노드 방문:
   • 현재 노드를 방문하고, 이 노드를 방문한 것으로 표시합니다.
4. 인접 노드 탐색:
   • 현재 노드와 인접한 노드를 스택에 추가하거나, 재귀 호출을 통해 방문합니다.
   • 이미 방문한 노드는 다시 방문하지 않도록 합니다.
5. 탐색 종료:
   • 모든 노드를 방문했으면 탐색을 종료합니다.

def dfs(graph, start):
    visited = set()  # 방문한 노드를 추적
    stack = [start]  # 스택에 시작 노드 추가

    while stack:
        vertex = stack.pop()  # 스택에서 노드 꺼내기
        if vertex not in visited:
            print(vertex)  # 현재 노드 처리 (예: 출력)
            visited.add(vertex)  # 노드를 방문한 것으로 표시
            stack.extend(graph[vertex] - visited)  # 인접 노드를 스택에 추가

    return visited

 

재귀사용

def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    print(vertex)  # 현재 노드 처리 (예: 출력)
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

BFS(너비 우선 탐색)

필수 개념

1. 큐: BFS는 큐 자료 구조를 사용하여 구현됩니다. 이는 FIFO(First In First Out) 방식으로 작동합니다.
2. 레벨 순서 탐색: BFS는 시작 노드에서부터 인접한 노드를 차례로 탐색하며, 각 노드를 레벨 순서로 방문합니다

필수 지식

1. 그래프 표현: 그래프를 인접 리스트 또는 인접 행렬로 표현할 수 있어야 합니다.
2. 방문 여부 확인: 노드가 이미 방문되었는지 확인하기 위해 방문 배열이나 집합을 사용할 수 있습니다.
3. 큐 사용법: 파이썬의 collections.deque를 사용하여 큐를 효과적으로 구현할 수 있습니다.

DFS와 BFS의 비교

BFS의 기본 로직

1. 초기화:
   • 시작 노드를 지정하고, 방문 여부를 추적할 자료 구조를 초기화합니다. 큐를 사용합니다.
2. 탐색 시작:
   • 시작 노드를 큐에 추가하고, 방문 여부를 추적합니다.
3. 노드 방문:
   • 큐에서 노드를 꺼내고, 이 노드를 방문한 것으로 표시합니다.
4. 인접 노드 탐색:
   • 현재 노드와 인접한 노드를 큐에 추가합니다. 큐에 추가하기 전에 해당 노드가 이미 방문되었는지 확인합니다.
5. 탐색 종료:

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드를 추적
    queue = deque([start])  # 큐에 시작 노드 추가
    visited.add(start)  # 시작 노드를 방문한 것으로 표시

    while queue:
        vertex = queue.popleft()  # 큐에서 노드 꺼내기
        print(vertex)  # 현재 노드 처리 (예: 출력)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)  # 노드를 방문한 것으로 표시
                queue.append(neighbor)  # 인접 노드를 큐에 추가

    return visited

코드 작성 시 고려할 점

1. 그래프 표현:
   • 그래프를 어떻게 표현할 것인지 결정합니다 (인접 리스트 또는 인접 행렬).
2. 방문 여부 확인:
   • 노드가 이미 방문되었는지 확인하고, 중복 방문을 방지합니다.
3. 자료 구조 선택:
   • DFS: 스택 또는 재귀
   • BFS: 큐
4. 기본 작업 처리:
   • 노드를 방문할 때 해야 할 기본 작업 (예: 출력, 결과 저장 등)을 정의합니다.
5. 기저 조건 설정:
   • DFS에서는 재귀 호출의 종료 조건을 설정하고, BFS에서는 큐가 비어 있을 때까지 탐색을 계속합니다.