DFS : 깊이 우선 탐색

• 다음 분기로 넘어가기 전에 해당 분기를 완벽히 탐색하는 방법이다.
• 모든 노드 방문 여부 반드시 검사해야 한다.
• 순환 알고리즘 (= 재귀) 형태를 가진다.
• 구현방법
  
  • 스택 
  • 재귀함수
  • 인접 행렬, 인접 리스트

def dfs(v):
    discovered = []
    stack = [v]

    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in sorted(graph[v], reverse=True):
                stack.append(w)
    return discovered

    print(dfs(1))
    
    graph = [[], [2, 3, 4], [3, 5, 6], [2], [2], [3], [3]]

 

# 재귀
def DFS(graph, v, visited, discovered):
    # 현재 위치 노드를 방문 처리
    visited[v] = True
    discovered.append(v)  # 방문하고 나서 적기
    for i in graph[v]:
        if not visited[i]:
            # discovered.append(i) # 방문하기 전에 적기
            DFS(graph, i, visited, discovered)

    return discovered


visited = [False] * len(graph)

v = 1
discovered = []

print(DFS(graph, v, visited, discovered))

 

▶ set 함수 https://wikidocs.net/16044

graph = {
    1: set([2, 3, 4]),
    2: set([3, 5, 6]),
    3: set([2]),
    4: set([2]),
    5: set([3]),
    6: set([3]),
}

▶ sort와 sorted

▶ dict와 list 에 따라서도 풀이법이 달라질 수 있다.

▶ 데이터타입 핸들링에 더더 익숙해지자.