ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 파이썬 자료구조 알고리즘, DFS -> 재귀함수로 구현
    Python 2024. 7. 21. 20:55

    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, []))

     

     

     

Designed by Tistory.