파이썬 자료구조 알고리즘, DFS -> 재귀함수로 구현

DFS

 

Depth First Search 깊이 우선 탐색 이라는 뜻으로, 아래와 같이 노드가 갈 수 있는 깊이만큼 계속 가다가 길이 없으면 다시 백해서 다른 방향을 탐색해서 가는 구조를 말한다.

 

 

DFS를 구현하는 방법은 재귀함수로 구현하는 방법과 스택으로 구현하는 방법 두가지가 있는데

 

재귀함수로 코드를 짤 때, 가장 중요한 포인트는 두가지이다.

 

1. 반복적으로 발생하는 일이 뭔지 아는 것

2. 종료 조건을 아는 것

각각의 숫자는 노드

 

노드 1을 방문하고 2, 5, 9 차례대로 방문할거다. 근데 2에 방문 했는데 2한테 자식이 있으니까 5한테 가기 전에 2의 자식인 3한테 가고 3의 자식인 4한테 갔다가 더이상 자식이 없음을 확인 후 백해서 2로 온 후 다른 자식이 있는지 확인하고 없으면 5한테 가는 순이다. 즉 반복적으로 발생하는 일은 노드에 자식이 있는지 확인하는 일이다. 

그리고 종료조건은 현재 노드가 이미 방문했던 노드인지 확인하는 것이다.

 

그럼 일단 위 그래프를 딕셔너리로 작성해보면 이렇게 된다.

키를 노드로, 키의 밸류를 노드의 인접 노드 리스트로 

graph = {
1: [2, 5, 9],
2: [3],
3: [4],
4: [],
5: [6, 8],
6: [7],
7: [],
8: [],
9: [10],
10: [],
}

 

그럼 이제 재귀함수로 코드를 짜보자.

 

일단 필요한 건 두 가지.

1. 지금 방문한 현재 노드 

2. 여태까지 방문했던 노드

 

여태까지 방문했던 노드에 append로 지금 방문한 현재 노드를 추가해준다.

# 현재 노드와 여태까지 방문했던 노드 두가지가 필요
def dfs_recursive(node, visited):
    # 방문한 노드 기록 (여태까지 방문한 노드에 현재 노드 추가)
    visited.append(node)

 

이제 인접 노드를 방문하면 된다.

1의 인접노드인 2, 5, 9 가 첫 방문이면 재귀함수를 호출하고, 방문한 적이 있으면 반복문을 종료하고 여태까지 방문했던 노드 visited를 반환한다.

    # 현재 노드의 모든 인접 노드를 방문하는 반복문
    for adj in graph[node]:
        # 인접 노드가 여태까지 방문했던 노드에 없으면 (즉, 첫 방문이면)
        if adj not in visited:
            # 인접노드를 시작 노드로 재귀함수 호출
            dfs_recursive(adj, visited)

    # 여태까지 방문했던 노드 리스트 반환
    return visited


print(dfs_recursive(1, []))

 

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

코드 실행 후 코드는 이렇게 동작한다.

 

시작

• dfs_recursive(1, [])이 실행되면 노드 1에 방문하여 visited 리스트에 추가되고, 1의 인접노드인 [2, 5, 9] 에 대해 반복을 시작한다.

 

1 의 인접노드 2 방문

• 2 방문 > 첫 방문이니까 > 재귀함수 dfs_recursive(2, [1]) 호출
• 2의 인접노드인 3 방문 > 첫 방문이니까 > 재귀함수 dfs_recursive(3, [1, 2]) 호출
• 3의 인접노드인 4 방문 > 첫 방문이니까 > 재귀함수 dfs_recursive(4, [1, 2, 3]) 호출
• 4의 인접노드 없음

 

백 트래킹

• 2로 돌아가서 > 2의 다른 인접노드 확인 > 없음
• 노드 5로 넘어감
• dfs_recursive(5, [1, 2, 3, 4]) 호출
• 5의 인접노드인 6 방문 > 첫 방문 > 재귀함수 dfs_recursive(6, [1, 2, 3, 4, 5]) 호출

이런 순서로 반복된다.

 

 

[전체코드]

graph = {
1: [2, 5, 9],
2: [3],
3: [4],
4: [],
5: [6, 8],
6: [7],
7: [],
8: [],
9: [10],
10: [],
}

# 현재 노드와 여태까지 방문한 노드 두가지가 필요
def dfs_recursive(node, visited):
    # 방문한 노드 기록 (여태까지 방문한 노드에 현재 노드 추가)
    visited.append(node)

    # 현재 노드의 모든 인접 노드를 방문하는 반복문
    for adj in graph[node]:
        # 인접 노드가 여태까지 방문했던 노드에 없으면 (즉, 첫 방문이면)
        if adj not in visited:
            # 인접노드를 시작 노드로 재귀함수 호출
            dfs_recursive(adj, visited)

    # 여태까지 방문했던 노드 리스트 반환
    return visited

print(dfs_recursive(1, []))