그래프 순회 - 2. BFS에서 이어집니다.
재귀 DFS에 대하여 얘기하기에 앞서
# 처음 인자값으로 넣어줄 visited 선언. 순회한 정점을 받는 리스트.
# 함수 안에 선언 시 초기화 되므로 전역변수로 선언
visited = []
# 함수선언
def dfs_recursive(node, visited)
# 함수의 인자로 받은 정점은 visited에 추가
visited.append(node)
# 정점이 가리키는 모든 점을 순회
for adj in graph[node]:
# 만약 순회하려는 점이 visited안에 없다면(방문한 적이 없다면)
if adj not in visited:
# 순회하려는 점을 인자값으로 함수 재실행(더 깊숙히 탐색)
dfs_recursive(adj, visited)
# 함수 정점이 가리키는 모든 값을 순회하면 visited 값 반환
return visited 재귀함수를 활용한 DFS는 구현 코드가 매우 단순하다. 우선 시작점으로 할 노드를 하나 함수에 인자로 넣는다. 그리고 그래프에서 해당 노드를 키 값으로 가리키는 값들을 받아, 값들을 시작 노드로 재설정하는 노드를 실행시킨다. 노드가 가리키는 값들은 또 새로운 가리키는 값들을 가져오고, 새로운 가리키는 값들을 시작점으로 다시 더 새로운 가리키는 값들을 가져오고, 또 더 새로운 가리키는 값들을 키값으로 더 더 새로운 가리키는 값들을 가져온다.
중요한 것은 새로운 키 값들을 가져올 때마다, visited가 업데이트 된다는 점이다. 사실 재귀 DFS 자체는 그다지 어려운 개념으로 느껴지지 않았다. 응용 문제를 만나기 전까는 말이다... 재귀에 대해서 매우 기초적인 지식만 이해하고 있었다. 재귀함수의 인자값을 전달하는 문제나 함수 내에서 함수를 호출하는 문제까지 뒤섞이고 나니 재료를 알 수 없는 맛있는 비빔밥이 되어있었다. 나는 무슨 재료가 들어갔는지 맞추는 장금이의 심정으로 여정을 시작했다.
재귀함수
재귀 함수를 볼 때마다, 위 사진처럼 끝이 어디인지 궁금한 마음이 생긴다. 재귀함수는 내가 동시에 감당할 수 있는 정보의 크기가 얼마인지, 저장공간의 그릇을 끊임없이 시험한다. 그렇지만 그건 사실 비효율적이고 잘못 된 접근이다. 재귀함수를 이루는 요소들을 알고, 반복의 파도를 타는 것이 중요하다. 그러려면, 재귀함수가 일반적인 함수와 다르게 작용하는 것들을 알 필요가 있다.
재귀함수를 이루는 요소들
내가 파악한 재귀 함수는 위의 네 가지 요소를 가진다. 어느 하나가 우선순위를 가진다기 보단, 네 가지가 있어야 재귀함수가 의미를 갖는다.
-
함수호출
- 첫 째 함수 호출은 재귀함수가 성립하기 위한 필수 조건이다. 함수가 진행되는 과정에서 혹은 결과 값으로 함수를 호출해야만 하는 당연한 이야기다. 종료조건은 성립 된 재귀함수가 원하는 만큼만 호출되어, 원하는 값을 도출할 수 있도록 설정해야 한다.
-
종료조건
- 종료조건이 없는 경우, 언어나 에디터 혹은 컴퓨터가 허락하는 만큼 깊은 함수호출을 하다가 어떠한 코드 외의 사유에 의해 정지될 것이다. 종료 조건은 여러가지 방법으로 설정할 수 있다. 함수 호출을 조건문을 통해 제어할 수도 있고, 함수에 특정 인자값이 들어왔을 때 재귀를 그만두고 특정 값을 반환할 수도 있다.
-
축적 값
- 어쩌면, 재귀함수라는 개념이 존재하는데 가장 중요한 요소이다. 일반적으로 잘 알려진 피보나치 수열의 구현 함수처럼 반환 값이 더해지는 축적도 있지만, 변수에 담긴 수 혹은 리스트의 요소가 반복적으로 갱신되는 형태로도 구현할 수 있다.
-
인자 값의 변화
- 인자값의 변화는 위의 종료조건과 축적 값이 보다 효율적으로 구현되기 위한 효과적인 방법이다. 물론 위의 세 가지 요소에 비해, 인자 값의 변화는 호출 함수 자체에 드러나지 않거나 없을 수도 있다. 인자로 들어가는 변수 값이 갱신되는 경우도 더러 있으니, 함수의 로직을 잘 따라가는 것이 중요하다.
재귀함수를 이용한 DFS를 다시 뜯어보자
# 축적 값을 담을 변수 선언[3]
visited = []
def dfs_recursive(node, visited):
# 값 축적 [3]
visited.append(node)
for adj in graph[node]:
# 종료조건 - 1 => adj가 visited에 있으면 종료 [2]
if adj not in visited:
# 함수 호출 [1]
# 인자 값이 node에서 adj로 바뀜. 매 재귀마다 adj > node로 변경되고
# node를 키 값으로 불러온 adj가 새로운 인자로 들어간다. [4]
dfs_recursive(adj, visited)
# 종료조건 -2 visited 반환하며 마무리 [2]
return visitedBack Tracking
Back Tracking은 조건에 맞는 정점을 찾아가는 와중에 해당 정점으로부터의 깊이 탐색이 원하는 조건을 충족시키지 못할 경우, 해당 탐색을 더 이상 탐색하지 않도록 하는 알고리즘입니다. 앞서 말한 재귀함수의 측면에서 얘기하면, 종료 조건을 하나 더 설정해주는 방식으로 구현할 수 있습니다.
DFS 탐색으로 그래프의 노드를 탐색하는 도중, 김재만이라는 이름을 값으로 가진 정점을 피하고 싶다면 아래와 같이 추가할 수 있습니다.
# 축적 값을 담을 변수 선언[3]
visited = []
def dfs_recursive(node, visited):
# 값 축적 [3]
visited.append(node)
for adj in graph[node]:
# 종료조건 - 1 => adj가 visited에 있으면 종료 [2]
if adj not in visited:
# 추가 된 종료조건(Back Tracking)
if adj.val == "김재만" :
continue
# 함수 호출 [1]
# 인자 값이 node에서 adj로 바뀜. 매 재귀마다 adj > node로 변경되고
# node를 키 값으로 불러온 adj가 새로운 인자로 들어간다. [4]
dfs_recursive(adj, visited)
# 종료조건 -2 visited 반환하며 마무리 [2]
return visitedBack Tracking의 효용
Back Tracking은 재귀 함수가 많이 호출되지 않은 단계에서 작동할 수록, 엄청난 횟수의 계산을 생략하도록 만듭니다. 스택으로 구현한 DFS, 큐로 구현한 BFS와 유의미한 계산 시간의 차이를 보일 수 있습니다. 단순한 아이디어로 구현되었지만, 해당 조건을 종료조건 뿐만 아니라 값의 축적이나 인자값의 변화와도 연결지을 수 있습니다.
마무리
흐르는 진도를 거꾸로 거슬러 오르는 선원들처럼..
