BFS 풀이 불가능 or 비효율 인 경우 (DFS 로 해결)

백엔드&인프라 추종자·2025년 4월 2일

BFS DFS

코딩테스트 공부

목록 보기

3/10

BFS로 풀이가 불가능하고 DFS로만 해결해야 하는 경우는 다음과 같습니다.

1. DFS가 필수인 경우 (BFS 사용 불가능)

✅ 1) 백트래킹 (모든 경우의 수 탐색)

정답을 찾을 때까지 모든 경우를 탐색해야 하는 문제
BFS는 모든 경로를 같은 레벨에서 동시에 탐색하므로 메모리 초과 발생 가능
DFS는 한 경로를 끝까지 탐색한 후 돌아오는 방식이므로 더 적은 메모리를 사용

🔹 예제 키워드

"모든 경우를 탐색해서 조건을 만족하는 경우를 찾으시오."
"백트래킹을 사용해 가능한 모든 경로를 탐색하시오."

✔ 예제 문제

N × N 체스판에서 N개의 퀸을 서로 공격하지 않게 배치하는 경우의 수를 구하시오. (N-Queen 문제)

📌 🔥 DFS만 가능

BFS는 경로를 같은 레벨에서 탐색해야 하므로 불필요한 경우의 수도 탐색해야 함
DFS는 유망하지 않은 경우는 가지치기(Pruning) 가능, 불필요한 탐색을 줄일 수 있음

def n_queen(n):
    def is_safe(row, col, board):
        for r in range(row):
            if board[r] == col or abs(board[r] - col) == abs(r - row):
                return False
        return True

    def dfs(row, board):
        if row == n:
            solutions.append(board[:])
            return
        
        for col in range(n):
            if is_safe(row, col, board):
                board[row] = col
                dfs(row + 1, board)

    solutions = []
    dfs(0, [-1] * n)
    return len(solutions)

print(n_queen(8))  # 8-Queen 문제 해결

✅ 2) 특정 경로를 완전 탐색해야 하는 경우

한 번 방문한 노드를 다시 방문할 수 없는 경우, BFS는 모든 경로를 탐색해야 해서 비효율적
DFS는 깊이 우선으로 탐색하면서 최적의 경로를 찾을 수 있음

🔹 예제 키워드

"한 번만 방문할 수 있는 경로를 찾으시오."
"모든 가능한 경로를 조사하시오."

✔ 예제 문제

그래프에서 출발점과 도착점을 정하고, 중복 없이 한 번씩만 방문하여 도착하는 경로의 개수를 구하시오.

📌 🔥 DFS만 가능

BFS는 경로를 같은 레벨에서 탐색해야 하므로 각각의 경우를 나누어 처리하기 어려움
DFS는 경로별로 탐색 가능하며, 백트래킹으로 불필요한 경로를 제거 가능

def count_paths(graph, start, end, visited):
    if start == end:
        return 1
    
    visited.add(start)
    count = 0
    for neighbor in graph[start]:
        if neighbor not in visited:
            count += count_paths(graph, neighbor, end, visited.copy())
    
    return count

graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
print(count_paths(graph, 1, 4, set()))  # 가능한 경로 개수 출력

✅ 3) 깊이가 중요한 문제 (BFS로 해결 불가능)

BFS는 너비 우선 탐색이므로 "깊이"를 기준으로 하는 문제 해결이 어려움
DFS는 "깊이"를 조절하며 탐색 가능

🔹 예제 키워드

"가장 깊이 들어갈 수 있는 경로를 찾으시오."
"최대 깊이를 구하시오."

✔ 예제 문제

주어진 트리에서 가장 깊은 노드까지의 거리(깊이)를 구하시오.

📌 🔥 DFS만 가능

BFS는 같은 레벨을 먼저 탐색하므로 깊이를 직접 추적하기 어려움
DFS는 깊이를 추적하면서 탐색 가능

def max_depth(tree, node):
    if not tree.get(node):
        return 0
    return 1 + max(max_depth(tree, child) for child in tree[node])

tree = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}
print(max_depth(tree, 1))  # 트리의 최대 깊이

✅ 4) 사이클 탐색 (DFS 활용)

BFS는 같은 레벨을 우선 탐색하므로, 사이클을 탐지하기 어려움
DFS는 "한 경로를 계속 탐색"하면서 방문했던 노드를 다시 방문하면 사이클임을 확인 가능

🔹 예제 키워드

"사이클이 존재하는지 확인하시오."
"그래프에서 순환 구조를 찾으시오."

✔ 예제 문제

방향 그래프에서 사이클이 존재하는지 확인하시오.

📌 🔥 DFS만 가능

DFS를 사용하면 백트래킹을 통해 방문 경로를 기록하며 탐색

def has_cycle(graph, node, visited, stack):
    visited.add(node)
    stack.add(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle(graph, neighbor, visited, stack):
                return True
        elif neighbor in stack:
            return True  # 사이클 발견

    stack.remove(node)
    return False

graph = {1: [2], 2: [3], 3: [4], 4: [2]}  # 사이클 존재
print(has_cycle(graph, 1, set(), set()))  # True 출력

2. DFS가 더 효율적인 경우 (BFS는 가능하지만 비효율적)

✅ 1) 그래프에서 모든 경로 탐색

DFS는 한 경로를 탐색한 후 백트래킹 가능
BFS는 모든 경우를 저장해야 하므로 메모리 초과 가능

✔ 예제 문제

"출발점에서 도착점까지의 모든 가능한 경로를 찾으시오."

📌 🔥 DFS가 더 효율적

BFS는 경로를 저장해야 하므로 메모리 초과 가능성 높음

✅ 2) 트리 탐색 (부모-자식 관계)

DFS는 자연스럽게 부모-자식 관계를 따라 탐색 가능
BFS는 같은 레벨을 탐색해야 하므로, 특정 노드의 부모를 찾기 어려움

✔ 예제 문제

"트리에서 특정 노드의 부모를 찾으시오."

📌 🔥 DFS가 더 효율적

DFS는 부모에서 자식으로 탐색 가능

3. 결론: DFS가 필수적인 경우 정리

유형	DFS가 필요한 이유
백트래킹 (모든 경우 탐색)	DFS는 가지치기가 가능해 최적화 가능
특정 경로를 완전 탐색	BFS는 불필요한 탐색이 많아 비효율적
깊이 우선 탐색이 필요한 경우	BFS는 너비 우선이라 깊이 탐색이 어려움
사이클 탐색	DFS는 방문 경로 추적이 가능

🚀 결론: "모든 경우를 탐색"하거나 "깊이 기반 문제"라면, BFS가 아니라 DFS를 사용해야 합니다. 😊