Base Line/알고리즘

DFS 업데이트

ylab 2022. 10. 25. 14:42
# dfs 기본 원칙
# 앞으로 찾아 가야할 노드와 이미 방문한 노드 기준으로 탐색
# 앞으로 찾아 가야할 노드면 계속 검색
# 이미 방문한 노드이면 무시하거나 따로 저장
# 구현 방식은 "스택/큐" or "재귀함수를 통해 구현" 

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

def dfs (graph, start_node):
    #두개의 리스트 별도로 관리
    need_visited = []
    visited = []

    #시작 노드를 시정하기
    need_visited.append(start_node)

    #방문이 필요한 노드가 있다면
    while need_visited:

        # 가장 마지막 데이터를 추출 (스택 구조를 활용)
        node = need_visited.pop()

        # 만약 그 노드가 방문한 목록에 없다면
        if node not in visited:
            
            # 방문한 목록에 추가하기
            visited.append(node)

            # 그 노드에 연결된 노드를
            need_visited.extend(graph[node])

    return visited

#print(dfs(graph,'A'))

from collections import deque
def dfs2(graph, start_node):
    visited = []
    need_visited = deque()

    ##시작 노드 설정
    need_visited.append(start_node)

    ##방문이 필요한 리스트가 아직 존재한다면

    while need_visited:
        ##시작 노드를 지정하고
        node = need_visited.pop()

        #만약 방문한 리스트에 없다면
        if node not in visited:

            #방문 리스트에 노드를 추가
            visited.append(node)

            need_visited.extend(graph[node])

    return visited


#print(dfs2(graph,'A'))

def dfs_recursive(graph, start,visited = []):
    visited.append(start)

    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)

    return visited

print(dfs_recursive(graph,'A'))