DFS 총정리

 

DFS(Depth First Search)

위에서 아래로 찾는 방식

 

그래프로 생각했을 때, 한 줄이 깊든 아니든 끝까지 다 검색하고 나서야 다음 줄로 넘어갈 수 있음. 

 

장점

1. 현재 탐색하고 있는 노드만 기억 -> 비교적 저장 공간에 대한 수요가 적다
2. 찾고자 하는 노드가 깊이 있는 경우, 너비 우선 탐색 방식보다 해를 더 빨리 구할 수 있음. 그러나 언제나 그런 것은 아닙니다. 찾고자 하는 노드를 맨 마지막에 와서 찾을 수도 있기 때문입니다.

단점

만일 깊이가 무한할 경우 해를 찾을 수 없을 가능성이 있음

해를 구하더라도 이것이 최적해(혹은 최단 경로 해)가 아닐 수 있음

해가 여러 개 존재하더라도 해를 구하면 탐색이 종료되기 때문입니다. 따라서 최단 경로 해를 찾고자 한다면 너비 우선 탐색을 사용하거나, 깊이 우선 탐색으로 구한 해의 경로를 따로 저장한 다음 최적해를 구해야 합니다.

 

규칙 두 가지

1. "앞으로 찾아야 가야할 노드"와 "이미 방문한 노드"를 기준으로 데이터를 탐색.
2. 특정 노드가 "앞으로 찾아야 가야할 노드"라면 계속 검색을 하는 것이고, "이미 방문한 노드"면 무시하거나 따로 저장

 

DFS의 구현방식 두 가지

1. 스택/큐
2. 재귀함수

 

 

제공해주신 데이터.

인접한 노드가 전부 연결되어 있음

A-B를 보면 알 수 있음.

 

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']

 

 

1-1) 리스트

def dfs(graph, start_node):
 
    ## 기본은 항상 두개의 리스트를 별도로 관리해주는 것
    need_visited, visited = list(), list()
 
    ## 시작 노드를 시정하기 
    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

 

 list에서 pop을 사용하면 성능면에서 좋지 않다고 한다.

따라서 논리는 거의 동일하지만 성능이 더 좋은 deque를 사용하는 것이 맞음.

(아래의 1-2와 비교해보면, 패키지 임포트와 need_visited가 데크로 정의된 것 말고는 전부 동일하다.)

 

 

 

1-2) 큐

# deque 사용
def dfs_deque(graph, start_node):
  # deque 패키지 
  from collections import deque
  visited = []
  # 방문이 필요한 쪽을 큐로 만들기
  need_visited = deque()
  
  # 시작 노드 설정
  need_visited.append(start_node)
  
  # 방문이 필요한 리스트가 아직 존재한다면
  while need_visited:
    # 시작 노드를 지정
    node = need_visited.popleft()
    # graph[node] -> 출처가 되는 곳이 node -> 도착점이 graph의 return치
    
    # 만약 방문 리스트에 없다면
    if node not in visited:
      # 방문 리스트에 노드를 추가
      visited.append(node)
      
      # 인접 노드들을 방문 예정 리스트에 추가
      need_visited.extend(graph[node])
  
  return visited

 

 

 

2) 재귀함수

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

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

 

 

해당 문제가 깊이 우선 탐색으로 풀 수 있는 문제였다...

def solution(numbers, target):
    global answer
    answer = 0
    def dfs(i,total):
        global answer
        print(i, total)
        if (i==len(numbers)):
            if total==target:
                answer+=1
                print("ans",answer)
            return
        dfs(i+1,total+numbers[i])    
        dfs(i+1,total-numbers[i])
        return
    dfs(0,0) 
    return answer

 

 

 

 

https://data-marketing-bk.tistory.com/44

DFS 완벽 구현하기 [Python]

https://kmight0518.tistory.com/24

[알고리즘 이론] 4. 깊이 우선 탐색(DFS)

 

참고로 한 블로그. 감사합니다.