DFS 풀이 불가능 한 경우 (BFS 로만 가능)

DFS 대신 무조건 BFS를 사용해야 하는 경우는 최단 거리(최소 이동 횟수)를 구하는 문제입니다. BFS는 가까운 노드부터 탐색하기 때문에, 최단 거리 문제에서 DFS보다 훨씬 효율적이고 정확합니다.

---

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

✅ 1) 최단 거리 문제 (최소 이동 횟수)

• 특정 시작점에서 목표 지점까지 가는 최소 이동 횟수를 구하는 문제
• BFS는 먼저 도달한 경우가 최단 거리이므로 최적의 해를 보장
• DFS는 깊이 우선 탐색이라 불필요한 경로를 탐색할 가능성이 높음

🔹 예제 키워드

"A에서 B까지 가는 최소 이동 횟수를 구하시오."
"최소 몇 번 만에 목적지에 도달할 수 있는가?"

✔ 예제 문제

1에서 N까지 이동할 때, 가능한 이동 방법이 {x + 1, x - 1, x * 2}라면 최소 몇 번의 이동으로 갈 수 있는가?

📌 🔥 BFS만 가능

• BFS는 가까운 거리부터 탐색하며, 가장 먼저 도착한 경로가 최단 거리

from collections import deque

def min_steps(n):
    queue = deque([(1, 0)])  # (현재 값, 이동 횟수)
    visited = set()

    while queue:
        x, steps = queue.popleft()

        if x == n:
            return steps
        
        for next_x in (x + 1, x - 1, x * 2):
            if next_x > 0 and next_x not in visited:
                visited.add(next_x)
                queue.append((next_x, steps + 1))

print(min_steps(10))  # 예제 출력

---

✅ 2) 가중치 없는 그래프에서 최단 경로 찾기

• 그래프에서 모든 간선의 가중치가 동일할 때 최단 경로를 찾는 경우
• BFS는 "먼저 방문한 노드가 가장 짧은 경로" 이므로 최단 거리를 보장
• DFS는 경로를 무작위로 탐색하므로 최단 거리 보장이 안 됨

🔹 예제 키워드

"한 노드에서 다른 노드까지 가는 최소 경로를 구하시오."
"BFS를 활용해 최단 이동 횟수를 찾아라."

✔ 예제 문제

N × M 크기의 미로에서 (1,1) → (N,M)까지 도달하는 최단 경로 길이를 구하시오.

📌 🔥 BFS만 가능

• BFS는 가까운 거리부터 탐색하며, 먼저 도착한 경로가 최단 거리

from collections import deque

def shortest_path(maze):
    n, m = len(maze), len(maze[0])
    queue = deque([(0, 0, 1)])  # (x, y, 이동 거리)
    directions = [(-1,0), (1,0), (0,-1), (0,1)]  # 상하좌우

    while queue:
        x, y, dist = queue.popleft()

        if x == n-1 and y == m-1:
            return dist

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1:
                maze[nx][ny] = 0  # 방문 처리
                queue.append((nx, ny, dist + 1))

maze = [
    [1, 1, 0, 1, 1],
    [0, 1, 1, 0, 1],
    [1, 0, 1, 1, 1],
    [1, 1, 1, 0, 1]
]
print(shortest_path(maze))  # 최단 거리 출력

---

✅ 3) 특정 조건을 만족하는 "최소 횟수" 문제

• BFS는 한 번의 이동에서 여러 방향으로 탐색하며, 가장 빠르게 도달하는 경우를 찾음
• DFS는 경로를 깊이 탐색해야 해서 비효율적

✔ 예제 문제

체스판에서 나이트가 한 지점에서 다른 지점까지 이동할 때, 최소 몇 번의 이동이 필요한가?

📌 🔥 BFS만 가능

• BFS를 사용하면 모든 방향으로 퍼져나가면서 최소 이동 횟수를 찾을 수 있음

from collections import deque

def knight_moves(start, end):
    moves = [(2, 1), (2, -1), (-2, 1), (-2, -1),
             (1, 2), (1, -2), (-1, 2), (-1, -2)]
    queue = deque([(start[0], start[1], 0)])  # (x, y, 이동 횟수)
    visited = set()

    while queue:
        x, y, steps = queue.popleft()
        
        if (x, y) == end:
            return steps
        
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            if (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append((nx, ny, steps + 1))

print(knight_moves((0, 0), (7, 7)))  # 최소 이동 횟수

---

2. BFS가 DFS보다 더 효율적인 경우

✅ 1) 최단 경로 찾기

• 그래프에서 최소 이동 거리를 찾아야 할 때
• BFS는 방문 순서를 보장하므로 최적의 해를 찾을 수 있음

✔ 예제 문제

A → B까지 가는 가장 짧은 경로를 찾으시오.

📌 🔥 BFS가 더 효율적

• DFS는 경로를 다 탐색해야 해서 시간이 오래 걸릴 가능성이 큼

---

✅ 2) 레벨별 탐색이 필요한 경우

• BFS는 한 단계씩 탐색하며 레벨을 관리할 수 있음
• DFS는 깊이 우선이라 레벨을 구분하기 어려움

✔ 예제 문제

K번 이동했을 때 가능한 상태를 구하시오.

📌 🔥 BFS가 더 효율적

• BFS를 사용하면 K번째 이동에서 도달할 수 있는 모든 상태를 확인 가능

---

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

유형	BFS가 필요한 이유
최단 거리 문제	BFS는 방문 순서가 거리 기준이므로 최단 경로 보장
가중치 없는 그래프에서 최단 경로	DFS는 깊이 탐색이라 최단 경로를 보장하지 않음
최소 횟수 문제	"최소 몇 번"과 같은 문제는 BFS가 필수
레벨별 탐색이 필요한 경우	BFS는 한 단계씩 탐색 가능, DFS는 비효율적

🚀 결론: "최단 거리"를 구해야 하는 문제라면, DFS가 아니라 BFS를 사용해야 합니다. 😊