비재귀 DFS

DFS. 참 유용하고도 많이 쓰이는 고마운 그래프 순회 알고리즘이다.

 

딱 하나 아쉬운 것이 있다면 재귀함수를 이용하기 때문에 파이썬에서 쓸 때는 좀 불편하다.

파이썬 유저들은 대부분 아래 상황을 겪어본 적이 있을 것이다.

 

 

1. DFS 코드 짜고, 제출 -> RecursionError

2. sys.setrecursionlimit 늘리기

2-1: AC(아주 낮은 확률, 그리고 시간을 간당간당하게 넘김)

2-2: PyPy일 경우, MLE

2-3: Python3일 경우, TLE

 

 

그래서 코드포스, 그리고 과거에 백준을 풀 때 이 문제때문에 골치가 아팠던 적이 있다.

이번 글에서는 DFS를 좀 더 빨리 돌려서 이 골치아픈 문제를 해결하는 방법을 3가지 알아보고자 한다.

 

1. C++ 배우기

파이썬은 아무래도 쉬운 대신 느린 언어다. 어렵지만 C++을 배우자.

 

2. 파이썬의 Generator를 이용한 Bootstrap Decorator

사실 가장 혁신적이고 간단한 방법같다.

나도 얼마전에 인터넷에서 찾았다. Codeforces에서 다른 유저들이 사용하는 것을 발견하여 블로그에 올리신 분의 블로그를 발견하여 나 역시 그분의 블로그를 블로그에 올리고자 한다.

https://heatz.tistory.com/13

 

3. DFS를 직접 비재귀로 구현하기

(이 블로그를 쓰는 이유)

사실 2번 방법을 써도 되지만 그래도 3번이 어쩔 수 없이 가장 빠르게 작동한다. 

2번은 그냥 코드를 복붙하면 되지만 3번은 문제에 따라서 직접 구현을 다르게 해야한다는 문제점이 있는데, 그래도 가장 빠른 방법이니만큼 블로그에 정리해서 올려본다. 

DFS의 스택 구현

우리가 알고있는 가장 기본적인 DFS 코드는 보통 아래와 같이 생겼다.

 

이때 스택을 이용해서, 방문하는 순서를 재귀 없이 쉽게 구현하는 방법이 있다. 재귀함수의 콜스택을 그냥 파이썬의 스택으로 구현한 것이 끝이다.

 

 

기본 DFS와의 차이점은,

1. visited 처리를 직접 노드를 처리하는 순서가 되기 전에 먼저 해주어야한다는 점. 불리자마자 다른 것은 무시하고 함수실행부터 하는 재귀함수와는 다르게 순서만 미리 정해놓는 것이기 때문.

 

2. 순회 순서가 조금 다르다는 점. 예를 들어 트리라고 하면, 같은 level의 노드에서의 순회 순서는 기존 DFS의 반대 순서이다.(이건 뭐 구현하기 나름이긴 하다)

이유는 아래 그림에서 알 수 있다.

하지만 결국에는 이것도 DFS다. 방문하는 순서만 조금 다른.

 

하지만 보통의 DFS 코드는 이것보다는 복잡한 경우가 대부분이다.

 

보통의 DFS 코드

보통의 DFS 코드들을 살펴보자. 보통은 구조가 아래와 같이 생겼을 것이다.

(아래는 코드포스 라운드 1096의 H번 문제에 쓰인 DFS 코드이다.)

 

 

이 구조를 분석해보면 대략 아래와 같이 할 수 있겠다.

 

 

쉽게 각 단계별로 번호를 매기겠다.

 

1. 방문(visited)처리

2. 자식노드 방문 전 처리

3. 자식노드 재귀호출 전 처리

4. 재귀호출

5. 자식노드 재귀호출 후 처리

6. 자식노드 모두 탐색 후 처리

7. 실제 DFS 실행

 

일반적으로 아마 모든 DFS 함수는 위와 같은 형태일 것이다.

이를 스택을 이용한 비재귀 형식으로 푸는 과정에서는 순서가 조금 바뀐다.

 

편의를 위해 현재 처리중인 노드를 n, 자식노드를 i라고 하겠다.

일단 1번 방문처리같은 경우는 위의 단순DFS 예시에서도 봤듯이, n번 노드를 직접 방문하기 전에 미리 자식관계(i)일때부터 일찍이 해주어야 한다.

 

4번 재귀호출같은 경우는 stack.append(i)로 대신한다.

 

7번 실제 DFS 실행같은 경우 따로 호출할 필요 없이 맨 처음에 stack에 처음 탐색할 노드를 넣고 시작한다.

 

 

2, 3번의 경우 재귀함수로 구현할 때와 스택으로 구현할 때의 순서가 크게 바뀌지 않는다.

 

문제가 되는 부분은 5, 6번의 부분이다.

 

 

다시 그림을 통해 차근차근히 알아보자.

우선, 위의 단순 예제를 통해 스택으로 DFS 방문 순서를 구하는 것은 쉽게 할 수 있을것이다. 이 방문 순서는 order라는 리스트에 저장되어있다고 하자.

 

 

2번 과정을 함수 A(n)으로 표현하고

3번 과정을 함수 B(n, i)으로 표현,

5번 과정을 함수 C(n, i)으로 표현,

6번 과정을 함수 D(n)으로 표현하자.

 

재귀함수 구현일 때 이 함수들이 실행되는 순서는 아래와 같을 것이다.

 

재귀호출이 진행되기 전인 A, B 함수의 실행 순서만 보았을 때,

A(1)

B(1, 2)

A(2)

B(2, 4)

A(4)

B(4, 8)

A(8)

B(2, 5)

A(5)

B(2, 6)

A(6)

...

 

이는 단순 order 리스트의 순서와 동일하다.

그러니까 A, B함수는 스택을 이용해서 순회를 하는 동안 DFS 함수에서의 절차와 똑같이 구현하면 된다는 것이다.

 

여기까지의 구현을 코드로 나타내면 다음과 같다.

 

C, D 함수의 실행 순서는 어떠할까?

먼저 비교적 쉬운 D함수만 보면

D(8)

D(4)

D(5)

D(6)

D(2)

D(7)

D(3)

D(1)

의 순서로 실행될 것이다.

 

이 순서는 어떤 순서인가?

만약 이 순서를 거꾸로 뒤집는다고 생각하면...

1 3 7 2 6 5 4 8

같은 level에서 방문 순서만 거꾸로인 DFS가 된다!

같은 level에서 방문 순서는 크게 중요하지 않으므로 결국 D 함수는 방문 순서의 역순으로 실행해주어도 아무 문제가 없는 것이다.

 

마지막으로, C 함수는 언제 실행되어야 좋은가?

C 함수 실행 순서만 보도록 하자.

C(4, 8)

C(2, 4)

C(2, 5)

C(2, 6)

C(1, 2)

C(3, 7)

C(1, 3)

 

뭔가 아까 본 듯한 수열이 보인다.

C(n, i)에서 i의 순서는 D의 순서, 즉 DFS 방문 순서의 역순과 동일하다.

그러니까 자식을 기준삼아서, 자신의 부모와 C 함수를 실행하면 좋은 구현이 될 것이다.

 

그 말은, 특정 노드의 부모를 저장해주는 parent 배열이 또 필요하다는 것이다.....

(DFS 순회 순서로 tree를 구성할 수 있음이 알려져있으므로 parent를 정의할 수 있다. 이때 DFS를 맨 처음에 시작한 노드가 루트가 된다.)

 

그리고 마지막 문단 for n in reversed(order) 아래에

C(parent[n], n)을 실행시켜주면 될 텐데

그렇다면 이 C 함수는 D 함수의 전에 실행되어야 할까? 아니면 후에 실행되어야 할까?

현재 n의 위치로만 따져보면

D 함수가 C보다 먼저 등장하므로

C 함수는 D 함수의 아래에 들어가는 것이 마땅하다.

 

그러면 최종적으로 코드가 완성된다.

재귀 풀기 전과 후를 비교해보면 아래와 같다.

재귀 풀기 전

 

재귀 풀고난 후

재귀를 풀었을 때 코드는 조금 더 길어지고 필요한 변수 리스트도 많아졌지만 그래도 시간은 빨라졌으니 이득이다(?)

 

 

추가

만약 DFS 함수가 리턴값이 있으면 어떠할까?

DFS[n] 리스트를 만들어서 리턴값을 임시로 리스트에 저장해놓는 식으로 dp처럼 구현할 수 있을것이다....이건 알아서 해보자.

리턴을 어디서 하냐에 따라서 코드가 들어갈 위치가 조금씩 달라질 것이다.