[Python] DFS(깊이우선탐색) 알고리즘

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) 강의 - 인프런

위 강의의 내용을 정리한 글입니다.

 

 

DFS는 깊이 우선 탐색이라고 하는 알고리즘으로, 트리 구조를 탐색할 때 사용됩니다.

트리의 가장 높은 레벨까지 갔다가 더 이상 없어서 막히면 되돌아가는 동작으로 구현됩니다.

 

 

 

트리 순회

트리 순회 방법은 전위, 중위, 후위 순회의 3가지가 있는데 대부분의 문제는 전위 순회를 통해 풀고, 예외적으로 병합 정렬 문제에서는 후위 순회를 이용하기도 합니다.

 

이 과정은 중첩 반복문의 대체제이자 자기 자신을 호출하는 함수인 재귀함수를 통해 이루어집니다.

 

        1

  2         3

4  5     6  7

 

형태의 트리 구조가 있을 때 순회 방법에 따른 순서는

전위 순회(위->왼->오): 1 2 4 5 3 6 7

중위 순회(왼->위->오): 4 2 5 1 6 3 7

후위 순회(왼->오->위): 4 5 2 6 7 3 1

입니다.

 

여기서 전위 순회를 코드로 나타내면 다음과 같습니다.

def DFS(num):
    if num > 7:
        return
    else:
        print(num)    # 이 코드의 위치에 따라서 전위,중위,후위 순회가 정해진다.
        DFS(num * 2)    # 왼쪽으로 뻗어나가기 (8이 되었을 때 멈춘다.) 바로 아래 라인보다 먼저 실행되고 먼저 끝나므로, 4가 5보다 먼저 출력된다.
        DFS(num * 2 + 1)    # 오른쪽으로 뻗어나가기

if __name__=="__main__":
    n = 1
    DFS(n)

 

print(num) 이 DFS() 를 호출하는 부분보다 위에 있는지, 아래에 있는지에 따라 순회 방법이 결정됩니다.

 

DFS() 함수에서는 위의 예시처럼 먼저 if-else문을 통해 재귀가 끝나는 조건을 달아주는 것이 좋습니다.

위에서는 num이 7을 넘으면 뿌리를 더 이상 뻗지 않고 끊어 버렸습니다.

 

 

 

상태 트리

DFS 문제 중에는 부분집합을 구해야 하는 문제가 많은데요, 이런 문제를 푸는 방법은 상태 트리를 이용하는 것입니다.

부모의 값이 포함된 부분집합인지, 그렇지 않은 부분집합인지에 따라 2갈래로 나뉘어 각각 두 번 호출하고,

뿌리를 여러 개 내려야 하면 for문을 통해 여러 번 호출해야 하는데 이때 필요한 것이 상태를 체크하는 변수입니다.

 

내가 현재 레벨에서 어떤 쪽(2갈래라면 좌, 우 중 하나) 뿌리로 내려왔는지 기록하는 변수라고 생각하시면 됩니다.

그렇기에 상태 체크 변수는 트리 레벨 크기의 리스트여야 하겠죠.

 

부모의 값이 포함된 부분집합이면 1(좌측 뿌리로), 그렇지 않으면 0(우측 뿌리로) 이동한다고 생각합니다.

그러면 다음과 같은 코드를 작성할 수 있습니다.

def DFS(v):
    if v == n + 1:    # 끝까지 갔을 때(4까지)
        for i in range(1, n + 1):    # 1~3까지 돌면서 사용한다고 체크된 값만 출력한다. 
            if ch[i] == 1:
                print(i, end=" ")
        print()
    else:
        ch[v] = 1    # 부모의 값을 사용하는 부분집합으로 넘어간다는 의미 (먼저 여기부터 돌고, 끝까지 간다음 오른쪽 가지를 뻗는다.)
        DFS(v + 1)
        ch[v] = 0    # 사용하지 않는 부분집합으로 넘어간다는 의미
        DFS(v + 1)

if __name__ == "__main__":
    n = 3
    ch = [0] * (n)    # 부모의 값을 사용하는 부분집합인지 확인하기 위한 체크 변수
    DFS(1)

 

 

 

 

탐색 시간을 줄이기 위한 방법

내가 원하는 조건의 부분집합을 찾기 위해서 모든 뿌리를 탐색할 때 불필요하게 시간이 많이 걸릴 수가 있습니다.

그래서 더 깊은 뿌리를 탐색하기 전에 해당 탐색이 불필요하다고 판단되면 더이상 뿌리를 뻗지 않고 멈추는 것이 효율적입니다.

 

예를 들어, 내가 원하는 부분집합이 있는지 존재를 "판단" 하는 것만이 문제의 끝이라면, 존재하는지 밝혀졌을 때 sys.exit(0)으로 프로그램을 바로 종료시켜 버리는 것도 하나의 방법입니다.

 

다음 코드는 수열이 주어졌을 때 이를 임의의 2개의 부분집합으로 나눴을 때 그 2개의 합이 같은 경우가 존재하는지 판단하는 문제의 DFS 함수입니다.

def DFS(L, sum):
    if sum>total//2:    # 시간 복잡도를 줄이기 위해, sum이 전체 합계의 절반을 넘으면 뿌리를 끝까지 내리지 않고 바로 컷
        return
    if L==n:
        if sum==(total-sum):
            print("YES")
            sys.exit(0)    # 프로그램을 바로 종료시키는 코드
    else:
        DFS(L+1, sum+a[L])
        DFS(L+1, sum)

 

이 문제에서는 부분집합 하나의 합이 수열 전체 합계의 딱 절반이 되어야 하는 문제입니다.

만약 수열 전체 합계의 절반을 넘는다면 더 이상 뿌리를 내려 합계에 포함시킬 이유가 없기에 뿌리를 더 이상 내리지 않고 끊어 버립니다.

 

그리고 존재한다는 것이 밝혀졌다면 프로그램을 바로 종료시켜버려 그 뒤의 남은 코드들을 굳이 실행시키지 않고, 결국 시간 비용을 절약하는 효과를 가져옵니다.

 

이렇게 시간을 줄일 수 있는 조건을 생각해 보는 것이 DFS 문제에서 보이는 Time exceed를 해결할 수 있는 방법입니다.