티스토리 뷰
- DFS vs BFS 각각 언제 사용해야 할까?
개인적으로 탐색 문제의 경우 1. 완전 탐색 -> 2. DFS -> 3. BFS 으로 시도해봄
| 기준 | DFS | BFS |
| 탐색 방식 | 한 경로를 끝까지 탐색 후 백트래킹 | 같은 레벨을 먼저 탐색 |
| 자료구조 | 스택(Stack) / 재귀(Recursion) | 큐(Queue) |
| 시간 복잡도 | O(V + E) | O(V + E) |
| 사용 예시 | 경로 탐색, 백트래킹, 사이클 판별 | 최단 경로 탐색, 레벨별 탐색 |
| 적합한 경우 | 경우의 수 탐색, 트리 탐색 | 최단 거리, 미로 탐색, 다차원 탐색 |
✅ DFS는 모든 경로를 탐색해야 하는 경우
✅ BFS는 최단 거리 탐색이 필요한 경우
✅ DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프 탐색에서 가장 많이 사용되는 알고리즘
✅ 각각의 장점과 사용해야 하는 문제 유형을 이해하는 것이 중요!
🚀 1️⃣ DFS (Depth First Search, 깊이 우선 탐색)
-> 방문 처리를 해주는 것이 핵심! 아니면 이미 방문한 노드를 끊임 없이 검사
visited = [False] * (N + 1)
def dfs(node):
visited[node] = True # 방문 처리
for neighbor in graph[node]:
if not visited[neighbor]: # 방문하지 않은 경우에만 탐색
dfs(neighbor)keyword : 스택 , 재귀 사용 (시간 조건과 종료 조건 명확하게 명시)
✅ DFS란?
- "깊이 우선 탐색": 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방식
- 재귀(Recursion) 또는 스택(Stack)을 활용
- 그래프의 모든 노드를 탐색하는 데 사용
- O(V + E) (노드 개수 V, 간선 개수 E)
✅ DFS를 사용해야 하는 문제 유형
| 1. 그래프에서 연결 요소 찾기 | 그래프가 몇 개의 연결된 부분으로 이루어졌는지 찾기 |
| 2. 경로 탐색 (모든 경우의 수 탐색) | 미로 탐색, 특정 조건을 만족하는 경로 찾기 |
| 3. 백트래킹 (Backtracking) | 모든 경우의 수를 탐색할 때 (예: N-Queen 문제) |
| 4. 사이클 탐지 | 트리인지 확인할 때 (방문했던 노드를 다시 방문하면 사이클) |
| 5. 위상 정렬 (Topological Sort) | 방향 그래프에서 정렬된 순서 찾기 (DAG) |
| 6. 트리 탐색 (Tree Traversal) | 전위, 중위, 후위 순회 (Preorder, Inorder, Postorder) |
🚀 2️⃣ BFS (Breadth First Search, 너비 우선 탐색)
keyword : queue ,
- BFS는 최단 경로 탐색에 자주 사용됨 (예: 미로 찾기, 게임 맵 최단 거리)
- visited를 사용하면 이미 최단 거리로 방문한 노드를 다시 탐색하지 않음!
from collections import deque
def bfs(start):
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if not visited[neighbor]: # 방문하지 않은 경우에만 탐색
visited[neighbor] = True
queue.append(neighbor)
✅ BFS란?
- "너비 우선 탐색": 가까운 노드부터 탐색하며, 한 레벨씩 진행
- 큐(Queue)를 활용
- 최단 거리(Shortest Path) 탐색에 유리
- O(V + E) (노드 개수 V, 간선 개수 E)
✅ BFS를 사용해야 하는 문제 유형
| 1. 최단 거리 찾기 | 미로 찾기, 최단 이동 횟수 찾기 (O(V+E)) |
| 2. 최단 경로 (가중치 없는 그래프) | 가중치가 없을 때 BFS가 최적 |
| 3. 레벨 탐색 (Level Order Traversal) | 트리에서 특정 깊이의 노드 탐색 |
| 4. 다차원 탐색 (2D/3D 배열 탐색) | 미로 탐색, 퍼즐 문제, 불 퍼뜨리기 |
| 5. 네트워크 흐름 분석 | 서로 연결된 노드들이 몇 개의 그룹으로 묶이는지 찾기 |
🚀 5️⃣ DFS & BFS 문제 추천
| 그래프 탐색 | 백준 1260번 - DFS와 BFS | DFS & BFS 구현 |
| 최단 거리 | 백준 2178번 - 미로 탐색 | BFS |
| 연결 요소 | 백준 11724번 - 연결 요소 개수 | DFS |
| 트리 탐색 | 백준 11725번 - 트리의 부모 찾기 | DFS |
| 최단 경로 | 백준 1697번 - 숨바꼭질 | BFS |
| 백트래킹 | 백준 9663번 - N-Queen | DFS |
* visited 배열이 필요 없는 경우
🚀 2️⃣ visited 배열이 필요 없는 경우
📌 ✅ 1) 그래프가 "트리 구조"인 경우 (N-1개의 간선)
- 트리는 사이클이 없으므로, 부모 노드에서만 방문하면 됨.
- 즉, visited 배열 없이도 탐색이 가능!
- 대신, 부모 노드(parent)를 인자로 넘겨서 중복 방문 방지 가능!
- 예시 코드 (DFS로 트리의 부모 찾기):
def dfs(node, parent):
for child in tree[node]:
if child != parent: # 부모를 다시 방문하지 않음 (visited 불필요)
parent_node[child] = node
dfs(child, node)✅ 트리 탐색은 visited 없이도 부모 정보만으로 충분히 탐색 가능! 🚀
📌 ✅ 2) 배열을 직접 변경하는 경우 (1 → 0으로 바꾸는 문제)
- 예: "미로 탐색" 문제처럼, 방문한 곳을 직접 1 → 0으로 변경하면 visited 불필요!
- 예시 코드 (maps[nx][ny] = 0으로 방문 처리)
def bfs(start_x, start_y):
queue = deque([(start_x, start_y)])
maps[start_x][start_y] = 0 # 방문 처리 (1 → 0)
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] == 1:
maps[nx][ny] = 0 # 방문 처리
queue.append((nx, ny))✅ 배열을 직접 수정하면 visited 배열 없이도 방문 여부를 알 수 있음! 🚀
🚀 3️⃣ visited 배열이 필요할 수도 있고, 필요 없을 수도 있는 경우
📌 ✅ 1) "사이클을 판별할 때"
- 그래프에서 사이클을 찾는 경우, visited가 필요함
- 하지만 트리에서는 visited 없이 부모 노드만 검사하면 됨
- 즉, "그래프"인지 "트리"인지에 따라 다름!
def has_cycle(node, parent):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if has_cycle(neighbor, node):
return True
elif neighbor != parent: # 부모가 아닌데 방문한 곳이면 사이클!
return True
return False✅ 그래프에서는 visited가 필요하지만, 트리에서는 필요 없음! 🚀
📌 ✅ 2) "DFS 탐색할 때, 중복 방문을 허용하는 경우"
def dfs(node, path):
path.append(node) # 경로 저장
for neighbor in graph[node]: # 방문 체크 없이도 탐색 가능
dfs(neighbor, path[:])- 어떤 문제에서는 같은 노드를 여러 번 방문해도 되는 경우가 있음 (예: 모든 경로 찾기)
- 이때는 visited 없이도 탐색 가능!
✅ 즉, "문제의 성격"에 따라 visited를 사용할지 결정! 🚀