[Algorithm] DFS & BFS

이번 포스팅에서는 코딩테스트에 자주 출제되는 그래프, 트리를 탐색하는 방법인 DFS(Depth-First Search)와 BFS(Breadth-First Search)에 대해서 소개하려고 한다.

DFS (Depth-First Search)

---

DFS는 하나의 노드에서 갈 수 있는 노드가 여러개 있다고 했을 때, 하나의 노드에 대해서 완벽하게 탐색하고난 후 다음 노드에 대해서 탐색하는 방법을 말한다. 좀 더 교과서적으로 정리해보자면 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 DFS라고 한다.

 

하나의 길로 쭈우우욱 가보고 막히면 돌아와서 다음 길로 가는 형태를 말한다.

 

보통 모든 노드를 방문해야 할 경우 DFS를 선택한다. DFS 알고리즘을 프로그래밍할 때는 일반적으로 재귀함수를 사용해 구현한다. Stack으로도 구현이 가능하지만 해당 포스트에서는 다루지 않는다.

 

DFS의 기본적인 의사코드를 살펴보자.

def dfs(current): # 현재상태를 표현하고 싶다면 인자를 통해서 배열이든 뭐든 전달하면 된다. (백트래킹 처럼!)
	visit[current] = True
    # 하고싶은걸 여기에 구현 (ex: 출력, 상태변화)
   	
    for i in range(1, N + 1):
    	# 1. 아직 방문하지 않았고, (여러 번 방문할 수 있다면 패스)
        # 2. 방문할 수 있다면, (2차원 배열로 그래프를 표현한 경우. Set으로도 표현할 수 있다)
    	if not visit[i] and matrix[current][i]:
        	dfs(i)

 

DFS의 장점은 직관적인 구현과 상태를 저장하기 쉽다는 것에 있다. 왜냐하면 재귀함수를 방문할 때마다 각자 다른 인자를 가지고 있기 때문에 인자를 통해서 상태를 표현하면 된다.

 

BFS (Breadth-First Search)

---

BFS는 하나의 노드에서 갈 수 있는 노드를 모두 탐색한 후 다음 깊이에 대해서 탐색하는 방법을 말한다. 즉, 시작지점에서 가까운 노드를 먼저 탐색하고 먼 노드를 나중에 탐색하는 방법이다.

 

보통 두 노드 사이의 최단 경로 및 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. BFS 알고리즘을 프로그래밍할 때는 일반적으로 큐(Queue)를 사용해 구현한다.

 

BFS의 기본적인 의사코드를 살펴보자.

def bfs():
	from collections import deque
    Q = deque([])  # 최초 시작 위치를 deque에 저장한다.
    
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while Q:
    	x, y = Q.popleft()
        
        # 노드에서 다음으로 갈 수 있는 반복
        for dir in dirs:
        	# 이동
            nx = x + dir[0]
            ny = y + dir[1]
            
            # 이동 범위에 대한 조건
            if not (0 <= nx < N and 0 <= ny < M):
            	continue
               
            # 이동 가능한지에 대한 조건
            if matrix[nx][ny] == -1:
            	continue
            # 기타 조건들을 여기에 넣으면 된다
            
            # 조건을 통해서 다음노드 추가할지 여부를 결정해도 된다
            # 상태 변경
            matrix[nx][ny] = matrix[x][y] + 1
            # Queue에 다음노드 추가
            Q.append([nx, ny])

위 예제에서 matrix를 2차원배열로 해도 되지만, 그래프를 인접 행렬로 표현해도 된다. 예를 들면 A에서 연결되는 노드가 B, C, D가 있으면 {A: [B, C, D]} 와 같이 표현해도 된다.

 

BFS에서 DFS처럼 하나의 요소마다 상태를 보관하고 싶다면 (x좌표, y좌표, 금액, 방향) 과 같이 Queue넣는 요소에 여러가지 상태를 포함시킬 수 있다. (좀 복잡해지긴한다...)

 

Python의 경우 재귀깊이에서 Recursive 에러가 발생할 수 있다. (Runtime Error)
그냥 기본적으로 재귀깊이를 늘려주는 코드를 추가해주도록 하자.

sys.setrecursionlimit(100000)