[알고리즘] DFS

DFS (Depth-First Search)

: DFS는 깊이 우선 탐색이다.
그래프에서 '깊은 부분'을 우선적으로 탐색하는 알고리즘이다.

A-B-D-E-F-C-G-H-I-J 순으로 순회.
(정점의 자식들을 먼저 탐색하는 방식)

알고리즘 구현

: 스택(need_visit),(visited) 자료구조에 기초하며,
재귀함수를 이용해 구현할 수도 있다.

1) 탐색 시작 노드를 스택(need_visit)에 삽입하고,
방문 처리(need_visit에서 꺼낸 후, visited에 삽입)한다.

2) 해당 노드의 인접 노드가 있으면, 그 인접 노드를 스택(need_visit)에 넣는다.

3) 스택(need_visit)에서 최상단 노드를 꺼낸 뒤, (visited에 있는지 확인하고 없으면) 방문처리 한다. 2)-3) 반복

*만약 방문한 적이 있다면(visited에 이미 있다면), 스택(need_visit)에서 다음 최상단 노드를 빼서 비교한다.

• 스택만 활용

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
    	cur_node = need_visit.pop()
        if cur_node not in visited:
            visited.append(cur_node)
            need_visit.extend(graph[cur_node])
            
    return visited

• 재귀함수 활용

def dfs(graph, cur_node, visited):
    # 현재 노드 방문 처리
    visited[cur_node] = True
    print(cur_node, end= ' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for node in graph[cur_node]:
    	if not visited[node]:
           dfs(graph, node, visited)
        
# 각 노드가 방문된 정보를 리스트 자료형으로 표현
visited = [False] * len(graph)
# 함수 호출
dfs(graph, start_node, visited)

시간 복잡도

: O(V+E)
노드 수(V)와 간선 수(E)를 더한 만큼 수행한다.

참고) Dave LEE 강의, <이것이 코딩 테스트다> 서적