4. DFS & 백트랙킹

DFS(깊이 우선 탐색 : Depth First Search)는 BFS와 더불어 그래프 탐색 알고리즘이며 주로 경로의 개념을 탐색할 때 쓰일 수 있는 기법이다. BFS(너비 우선 탐색)과의 큰 차이점은, 어느 한 지점으로 파고들면 그곳을 기점으로 더 파고들어 전부 탐색 후 그제야 방향을 바꿔서 다른 지점으로 파고드는 형식으로 탐색이 이뤄진다.

자바로 그래프를 구현한 후, 구현한 그래프에서 시작 노드와 도착 노드를 매개값으로 한 길찾기 메소드를 구현할 때 BFS와 더불어 DFS를 구현했었는데, 거기서 확인할 수 있었던 것은 BFS에 비해 DFS는 최단 경로 탐색이라는 목적에는 부합하지 않았다.

즉, 직선 도로와 우회 도로의 개념이 DFS에는 딱히 없으며 만약 우회 도로로 먼저 탐색을 시작하게 될 경우, 끝끝내 도착점에 닿을 때까지 우회 도로를 우선시하며 그 시점에서 직선 도로의 고려사항은 후순위로 밀려나가기 때문에 최단 경로 탐색에 DFS만을 활용하는 것은 무리가 있다.

그래서 단짝처럼 같이 고려되는 것이 백트랙킹이다. 특정 지점까지 닿았을 때, 그 지점으로부터 더 이상 탐색을 이어나갈 이유 혹은 가능성이 보이지 않으면 굳이 불필요하게 탐색을 이을 필요가 없으므로 중단하는 것이다. 대표적인 관련 문제가 N-Queen 문제인데, 나중에 풀어볼 예정.

1) 의사코드

우선, DFS와 백트랙킹에 대한 개념은 이미 숙지하고 있지만 그것을 문제 풀이에서 적용하는 것이 어려워서 DFS와 백트랙킹을 활용하는 문제의 풀이 방법에 대한 감각을 익히기 위한 목적으로 공부 기록 방향을 잡았다.

(1) DFS의 구현

DFS는 크게 반복문을 활용한 방법과 재귀를 활용한 방법으로 구현할 수 있다. 먼저, 내가 자바로 처음 구현했던 반복문 활용법의 의사코드를 간단하게 파이썬으로 작성한다면...

# DFS by Stack

방문_기록 = []
stack.append(시작_지점)

while stack:
	current = stack.pop()
	
    # 방문 여부 추적을 통한 중복 방문 방지
    if 방문_기록에 current가 없으면:
    	방문_기록.append(current)
        
        for current의 다음 노드들:
        	# current 역시 정답의 출력사항에 포함된다면
            # current를 이어붙인 새로운 값으로 변수 할당도 생각 가능
        	stack.append(다음 노드)

대략 이런 식으로 작성이 되며, 반복문의 종료 조건을 stack에 담긴 모든 방문 기록을 pop하게 되는 것이다. 다음은 연습이 좀 더 필요한 재귀 활용법의 의사코드다.

# DFS by recursion

# 방문_기록 = []

def recursive_dfs(지점, 방문_기록):
	current = 지점
	방문_기록.append(current)
    
    for current의 다음 노드들:
    	if 다음 노드 is not in 방문_기록:
        	# 재귀 호출 수행
        	recursive_dfs(다음 노드, 방문_기록)
    
    return 방문_기록
 
recursive_dfs(시작 지점, []) # 호출 시작

반복문을 활용한 DFS는 반복 분기(while)로 지속적인 탐색 작업이 이뤄지고, 재귀를 활용한 DFS는 재귀 호출로 지속적인 탐색 작업이 이뤄진다. 둘 다 특별한 조건이 없기 때문에 기본적으로 모든 그래프의 정점 노드를 전부 탐색하고 담겨진 방문 기록을 반환하는 매커니즘이다.

(2) 백트랙킹과의 결합

앞서 말했듯 의사코드로써 구현이 이뤄지면 결국 모든 노드를 순회 탐색하게 되는 일반적인 DFS 구현이 되고, 이는 사실 알고리즘 풀이에서는 크게 효용이 없다. DFS 하나만을 통해서는 최단 경로 탐색이라는 시간 효율적인 측면을 이뤄낼 수 없기 때문에 백트랙킹 결합이 필수적인 과정으로 들어간다.

그 전에 앞서, 백트랙킹을 수행하려면 어떻게 해야 될까? 백트랙킹이란 결국 현재 시점의 탐색을 강제 중단하는 건데, 강제 중단의 조건은 if문으로 산입한다고 해도, 결국 탐색을 중단시키는 코드가 필요하다.

반복문 DFS

특정 시점의 특정 노드에서의 방문 여부 조사 및 탐색이 이뤄지는 시점은 분기의 시작점인, stack에서 pop했을 때가 된다. 위의 이미지에서처럼 돌아가는 작업까지 생각하지 않아도 된다. 중단하고 다음 순서로 이뤄지는 것 자체가 이미 돌아가는 것과 마찬가지이기 때문.

stack에서 pop하고 말했던 탐색 시점은 결국 while문 내부의 if문에서 이뤄지고 있는데, 해당 과정을 건너뛰고 바로 다음 순회 단계로 넘어갈 수 있는 방법은 continue를 활용하면 되겠다.

재귀 DFS

특정 시점의 특정 노드에서의 방문 여부 조사 및 탐색이 이뤄지는 시점은 함수 내부에서의 재귀 호출이 된다. 함수가 호출됐다는 의미는 해당 단계의 매개값 노드가 방문되지 않았음이 판별됐다는 의미와 동일하다.

그렇다면 재귀 호출을 막는 것이 곧 백트랙킹이 될 수 있는데, 이를 실현시킬 수 있는 방법이 재귀 함수에서의 탈출 조건 설정이 될 수 있겠다.

위의 고찰 과정과 더불어 백트래킹 조건을 추가한 반복문 DFS의 의사코드 내용은 아래처럼 작성될 것이다.

# DFS by Stack with Backtracking

방문_기록 = []
stack.append(시작_지점)

while stack:
	current = stack.pop()
    
    # 백트래킹
    if current is 백트래킹 조건:
    	# current까지의 방문 기록 보관 등의 별도 작업
        continue
	
    # 방문 여부 추적을 통한 중복 방문 방지
    if 방문_기록에 current가 없으면:
    	방문_기록.append(current)
        
        for current의 다음 노드들:
        	# current 역시 정답의 출력사항에 포함된다면
            # current를 이어붙인 새로운 값으로 변수 할당도 생각 가능
        	stack.append(다음 노드)

마찬가지로 백트랙킹 조건을 추가한 재귀 DFS의 의사코드 내용은 아래처럼 작성될 것이다.

# DFS by recursion with Backtracking

# 방문_기록 = []

def recursive_dfs(지점, 방문_기록):
	current = 지점
    
    # 백트랙킹
    if current is 백트래킹 조건:
    	# current까지의 방문 기록 보관 등의 별도 작업
        return 방문_기록
    
	방문_기록.append(current)
    
    for current의 다음 노드들:
    	if 다음 노드 is not in 방문_기록:
        	# 재귀 호출 수행
        	recursive_dfs(다음 노드, 방문_기록)
    
    return 방문_기록
 
recursive_dfs(시작 지점, []) # 호출 시작

(3) 간략한 고찰

사실 알고리즘을 공식화해서 푸는 것은 내게는 양날의 검인 듯하다. 개념만을 알고 있다고 한들, 알고리즘은 약간 득도(...)의 영역에 가까운 파트이기도 하고 결국에는 개념을 실전에 적용해서 유연하게 코드로 푸는 과정이 필요하기 때문에 수없이 문제를 풀 수 밖에 없다.

현재는 시간이 그렇게 넉넉하지 않은 시점이기도 하고 성격상 1회독으로 끝낼 공부도 결코 아니기 때문에 그저 개념을 다시 다잡고 문제를 풀기 위한 방향의 지침 정도로만 삼으며 실전 감각을 익힐 준비에 더 집중하자.