[알고리즘] 파이썬 DFS/BFS 정리 및 예제 풀이

코딩테스트 기본 문제 DFS/BFS 

- DFS와 BFS는 코딩테스트 단골문제로 코딩테스트를 준비하는 사람이라면 반드시 알고 있어야 한다. 

- DFS와 BFS 모두 그래프 탐색 기법으로, 완전 탐색 알고리즘(Brute Force)의 일종이다. 

- 완전 탐색 알고리즘이므로, 시간의 제약이 있는 경우 DP나 heap 등을 이용해 시간을 줄여야 한다. 

- SWEA 기준 3~4 level(advanced등급) 시험에서는 DFS/BFS만 가지고 해결가능한 문제가 주로 나온다. 

- SWEA  5 level 이상(pro 등급) 시험에서는 DFS/BFS + DP 및 heap 등 추가 기법을 활용하는 문제가 주로 나온다.

 

DFS( Depth Firsrt Search : 깊이 우선 탐색 )

- DFS는 그래프 탐색 기법으로 루트 노드에서 하나의 가지(branch)를 정해서 모두 탐색한 후 다음 가지를 탐색한다. 

- DFS 구현에는 주로 재귀함수 or stack(후입선출)을 사용한다.  

- 아래 애니메이션의 숫자의 번호가 방문 순서이다. 

DFS 애니메이션 ( 출처 : 위키 )

DFS 재귀함수 예시 

def dfs_recursive(x):
    visited[x] = True ## 방문 노드 표시
    print(x)
    for nx in graph[x]: ## 현재 노드에 연결된 다음 노드 탐색
        if not visited[nx]: ## 다음 노드가 방문하기 전이라면
            dfs_recursive(nx) ## 재귀 함수 호출

## 예시 그래프
N = 10 # 총 노드 개수
graph = {1:[2,5,9], 2: [3], 3:[4],4:[],5:[6,8],6:[7],7:[],8:[],9:[10],10:[]}
visited = [0]*(N+1) ## 방문 표시
dfs_recursive(1) ## DFS 호출( 시작노드 )

 

- 재귀함수 구현 시에는 방문표시 조건을 잘 설정하여 반복 호출의 최대한도에 도달하여 에러가 발생하지 않도록 주의.

 

DFS Stack 예시 

def dfs_stack(x):
    stack.append(x) ## 시작 노드 스택에 추가
    while stack :
        nx = stack.pop() ## 다음 노드 stack에서 꺼내기
        if not visited[nx]: ## 다음 노드가 방문하기 전이라면
            print(nx)
            visited[nx] = 1 ## 다음 노드 방문 표시
            # stack.extend(graph[nx])## 다음노으의 자식노드들 스택에 추가
            stack.extend(reversed(graph[nx]))## 다음노으의 자식노드들 스택에 추가(역순)

## 예시 그래프
N = 10 # 총 노드 개수
graph = {1:[2,5,9], 2: [3], 3:[4],4:[],5:[6,8],6:[7],7:[],8:[],9:[10],10:[]}
visited = [0]*(N+1) ## 방문 표시
stack = [] ## 방문 노드를 담을 stack(list)공간
dfs_stack(1) ## DFS 호출( )

- 스택 구현시에는 python list의 pop 기능을 활용하면된다. pop은 가장 뒤에 들어온 원소를 뽑아내므로, 이를 주의하자.

 

BFS( Breadth Firsrt Search : 깊이 우선 탐색 )

- BFS는 그래프 탐색 기법으로 루트 노드에서 가까운 노드부터 탐색하는 방법이다. 

- BFS 구현에는 collections 패키지의 queue를 사용한다.( 선입 선출 )  

- 아래 애니메이션의 숫자의 번호가 방문 순서이다. 

BFS 애니메이션 ( 출처 : 위키 )

BFS 예시

from collections import deque
def bfs_queue(st):
    queue.append(st) ## 시작 노드 queue에 추가
    visited[st] = 1 ## 시작 노드 방문표시
    while queue :
        x = queue.popleft() ## 현재 노드 queue에서 꺼내기(먼저 들어온 것 부터)
        print(x, end=' ')
        for nx in graph[x]: ## 현재 노드에 연결된 다음노드 찾기
            if not visited[nx]: ## 다음 노드가 방문하기 전이라면
                visited[nx] = 1 ## 다음 노드 방문 표시
                queue.append(nx)

## 예시 그래프
N = 10 # 총 노드 개수
graph = {1:[2,5,9], 2: [3], 3:[4],4:[],5:[6,8],6:[7],7:[],8:[],9:[10],10:[]}
visited = [0]*(N+1) ## 방문 표시
queue = deque() ## 방문 노드를 담을 queue공간
bfs_queue(1) ## BFS 호출( 시작노드 )

 

자주 출제되는 BFS 예제와 풀이

- BFS 문제는 2d list 상에서 상/하/좌/우 방향으로 움직이며 최대/최솟값을 갖는 경로를 찾는 류의 문제가 많이 출제된다.

from collections import deque
move = [(-1,0),(1,0),(0,-1),(0,1)] ##2d list에서 상/하/좌/우 움직이는 방향

def bfs():
    queue = deque()
    queue.append((0,0)) ## 시작 노드 q에 추가
    distance[0][0] = arr[0][0] ## 시작 노드 거리 초기화
    while queue:
        x, y = queue.popleft() ## 현재 노드 꺼내기
        for dx, dy in move: ## 상/하/좌/우 방향으로 다음 노드 탐색
            nx = dx + x
            ny = dy + y
            if 0 <= nx < N and 0 <= ny < N: ## 다음 노드가 2d list 범위에 맞는지?
                # 만약 더 짧은 거리가 있다면 최소 거리로 갱신
                if distance[x][y] + arr[nx][ny] < distance[nx][ny]: ## 기존 nx,ny 까지의 거리와 이번에 업데이트할 거리 비교 
                    distance[nx][ny] = distance[x][y] + arr[nx][ny] ## 이번 업데이트 거리가 더 작으면 업데이트 
                    queue.append((nx, ny)) ## queue에 노드 추가 

N = int(input())
arr = [ list(map(int, input() ))  for _ in range(N) ] ## 문제에서 주어지는 2d list
distance = [[float('inf')] * N for _ in range(N)] ## 내가 찾아야할 경로 별 거리
bfs()

- 위 형식의 문제가 자주 출제되며, 위 형식에서 각종 조건이 추가되면 문제가 어려워 진다. 

- 추가 조건은 1) 탐색할 필요가 없는 노드를 가지치기하는 DP( Dynamic Programming ), 2) 우선순위를 이용하여 탐색하는 heapq 사용 형식이 자주 나오는 것 같다.