DFS 랑 BFS 언제, 어디서, 어떻게 쓰는 거임? (알고리즘 유형 정리)

이번 코테 벼락치기하면서 느낀 거. dfs bfs 는 그래프에서만 쓰이는 게 아니다~

ㄴ 진짜 몰 랐 어

 

DFS 는 탐색 (검색) 문제에서 "한 경로 끝까지 들어갔다가 다시 돌아오는 방식" 이다.

즉, 모든 경우의 수/경로를 전부 확인해야 할 때 자주 쓴다.

깊게, 끝까지 탐색하는 것이다. (재귀/스택)

 

반면에 BFS 는 "가까운 것부터 차례차례 넓혀 나가는" 탐색이다.

넓게, 가까운 곳에서부터 탐색하는 것이다. (큐)

최단거리 문제에 자주 사용된다.

 

DFS

경로 전체 탐색, 경우의 수 세기, 연결 요소 찾기, 순열/조합

1. 그래프/트리 탐색
   • DFS 는 한 갈래 끝까지 갔다가 못 가면 돌아오는 (backtracking) 방식이라, 트리/그래프 구조에 잘 맞음
2. 경로 찾기/모든 경우 탐색
   • 미로 탐색, 백트래킹 문제(N-Queen, 스도쿠, 단어 찾기)
3. 조합, 순열, 부분집합 생성
   • n 개 중에서 m 개 고르기, 부분집합 구하기, 문자열에서 가능한 조합 구하기
4. 연결 요소 찾기
   • 2 차원 배열에서 영역 (덩어리) 을 찾을 때
   • 그림의 개수(인접한 픽셀 모두 탐색), 바이러스 전파(인접 노드 모두 방문)

n, m = 5, 5
grid = [[0]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def dfs(x, y):
    visited[x][y] = True
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
            dfs(nx, ny)

BFS

최단거리 찾기, 연결 요소 찾기, 시간 순서대로 퍼져 나가기

1. 최단거리 문제
   • 가중치가 없는 그래프 최단거리
   • 미로 탐색, 게임 맵 최단거리
2. 최소 이동 횟수 찾기
   • 한 상태에서 다음 상태로 가능 방법이 여러 가지 있고, 최소 몇 번 만에 도착할 수 있는가?
   • 숫자 변환 및 단어 변환의 최소 단계
3. 레벨 탐색
   • BFS 는 한 번에 같은 "깊이"의 노드를 모두 방문
   • 트리 탐색에서 레벨 순서대로 출력이 필요할 때 사용
   • 이진 트리에서 각 레벨별 노드 출력, 그래프에서 k 단계 이내에 있는 노드 찾기
4. 최단 시간 문제
   • 어떤 상황이 시간에 따라 퍼져나가는 경우 (불, 바이러스, 전염, 물 확산 등)

from collections import deque

n, m = 5, 5
grid = [[0]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))