BFS/DFS 정리

 

BFS와 DFS의 기본이 되는 개념이 바로 그래프이다.

그래프 ?

: 정점(노드)와 간선으로 이루어진 자료구조를 의미한다. (  노드 : 실제 데이터 저장된 것 , 간선 : 노드 사이 연결하는 선 )

 그래프는 방향성, 비방향성, 가중치가 있는지 없는지에 따라서 다양한 형태를 갖는다. 

[ 그래프의 종류에 대해서 몇가지 정리하면 아래와 같다 ]

• 방향 유무(방향 그래프/ 무방향 그래프)
• 가중치 유무(가중 그래프 / 비가중 그래프)
• 사이클 유무(사이클릭 그래프. 에사이클릭 그래프)
• 유향 비순환 그래프
• 트리
• 포레스트
• 완전 그래프
• 서브 그래프
• 등등등

즉, 그래프 탐색을 수행하는 대표적인 방법으로 BFS와 DFS를 생각하면 된다. 

 

 

 

DFS ( 깊이 우선 탐색 ) ?

:  깊이 우선 탐색은 시작 노드에서 출발해서 한 경로를 따라 가능한 깊이까지 들어가서 노드를 방문하고 가능한 길(road)가 없을경우 다시 돌아와서 다른 경로를 탐색하는 방법이다. 

 

※ 주로  재귀호출 / 스택  사용해서 구현 

▶ 한가지 경로를 끝까지 탐색하니까 특정 경로가 존재하는지 확인할때 유리하고 전체 경로 탐색하는 경우에 적합한 방법이다.

 

dfs 예시

기본 DFS 패턴 ( 재귀 방식 ) 

def dfs(node, graph, visited):
    visited[node] = True  # 현재 노드를 방문 처리
    for neighbor in graph[node]:  # 인접한 모든 노드에 대해
        if not visited[neighbor]:  # 방문하지 않았다면
            dfs(neighbor, graph, visited)  # DFS 재귀 호출

 

 

 

BFS ( 너비 우선 탐색 ) ?

: 너비 우선 탐색은 모든 인접한 노드를 먼저 탐색한다. 큐를 사용해서 현재위치에서 가능한 모든 방향으로 오른 위치를 탐색하는 방법이다. 

 

※ 주로  최단 경로 찾는 문제 에 유리하다. 

▷ 넒게 퍼지면서 탐색하는 방법이라서 메모리 사용량이 많아질 수 있음 주의

 

bfs 예시

기본적 BFS 사용 ( 큐 활용 )

from collections import deque

def bfs(start, graph, visited):
    queue = deque([start])  # 시작 노드를 큐에 삽입
    visited[start] = True  # 시작 노드를 방문 처리
    
    while queue:  # 큐가 빌 때까지 반복
        node = queue.popleft()  # 큐에서 가장 먼저 들어온 노드를 꺼냄
        print(node)  # 현재 노드를 출력 (또는 다른 작업 수행)
        
        for neighbor in graph[node]:  # 인접한 모든 노드에 대해
            if not visited[neighbor]:  # 방문하지 않았다면
                queue.append(neighbor)  # 큐에 삽입
                visited[neighbor] = True  # 방문 처리

 

 

결론적으로 BFS/DFS는 노드를 방문하는 순서를 결정하는 중요한 도구로 사용된다고 이해하면 된다.