[Tip] 언제 DFS를 쓰고 언제 BFS를 써야할까? 💥💥

공통점

BFS와 DFS 모두 연결된 그래프를 “완전 탐색”하는데 활용

언제 DFS를 쓰고 언제 BFS를 써야할까?

BFS

• 큐 이용
• 최단 거리 문제

대표 문제

미로의 최단거리 통로

from collections import deque

N = 7 # 7*7 격자판
board = [list(map(int, input().split())) for _ in range(N)]
dist = [[0] * N for _ in range(N)] # ✅ 출발지로부터 거리 리스트 필요
visited = [[0] * N for _ in range(N)]

q = deque()
q.append((0, 0)) # 출발 지점
visited[0][0] = 1

dx, dy = [0,-1,0,1], [1,0,-1,0]
while q:
    cur = q.popleft()
    for w in range(4):
        xx, yy = cur[0]+dx[w], cur[1]+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        if board[xx][yy] == 1 or visited[xx][yy] == 1:
            continue
        q.append((xx, yy))
        visited[xx][yy] = 1
        dist[xx][yy] = dist[cur[0]][cur[1]] + 1 # ✅ 거리 업데이트

print([dist[N-1][N-1], -1][dist[N-1][N-1] == 0])

DFS

• 재귀 (또는 스택) 이용
• 모든 경우를 하나하나 다 탐색을 해야 될 경우 이용
  • 대표적으로 조합, 순열
• 이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 이용

대표 문제

순열 구하기

def DFS(L):
    global cnt
    if L == M:
        cnt += 1
        print(' '.join(map(str, res)))
    else:
        for i in range(1, N+1):
            if used[i] == 1:
                continue
            used[i] = 1
            res[L] = i
            DFS(L+1)
            used[i] = 0 # ✅ 다시 풀어주기
    
N, M  = map(int, input().split())

cnt = 0
res = [0] * M # ✅ 순열 결과
used = [0] * (N+1) # ✅ 사용한 수 체크

DFS(0)
print(cnt)

조합 구하기

def DFS(L, S): # ✅ start 지정
    global cnt
    if L == M:
        cnt += 1
        print(' '.join(map(str, res)))
    else:
        for i in range(S, N+1):
            if used[i] == 1:
                continue
            used[i] = 1
            res[L] = i
            DFS(L+1, i+1) # ✅ 다음 start에 (i+1)을 넘기기
            used[i] = 0

N, M = map(int, input().split())

res = [0] * M
used = [0] * (N+1)

cnt = 0
DFS(0, 1)
print(cnt)

장단점

BFS

⭕ 장점

• 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
• 최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.

❌ 단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

DFS

⭕ 장점

• 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.
• 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다.

❌ 단점

• 해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색한다.
• 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용한다.
• DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없다. DFS는 해에 도착하면 탐색을 종료하기 때문.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기