Algorithm/Brute-force (완전 탐색 기법) (3) 썸네일형 리스트형 깊이 우선 탐색(Depth-First Search) : DFS 깊이 우선 탐색(Depth-First Search) - 그래프 탐색 방법 중 한 가지 종류 "그래프 탐색은 BFS로 하는 것이 훨씬 쉽지만, 재귀함수 사용(백 트래킹에서 쓰임)을 익히기 위해서 DFS가 용이" Stack 사용 아이디어 - 시작점에 연결된 Vertex 찾기 - 찾은 Vertex를 계속해서 찾음(끝날 때까지) - 더이상 연결된 Vertex가 없을 경우 다음으로 넘어감 [그래프 예시] 파이썬으로 구현한 DFS 알고리즘 # 재귀함수로 구현한 DFS def dfs(graph, start, visited): visited[start] = True print(start, end=' ') for i in graph[start]: if visited[i] == False: dfs(graph, i, vis.. 백 트래킹(Back Tracking) 알고리즘 백트래킹(Back Tracking)이란? - 모든 경우의 수를 확인해야 할 때 => (ex) 순열 : for문으로는 확인 불가한 경우에 사용(깊이가 달라질 때) "깊이 우선 탐색(DFS)과 마찬가지로 스택(Stack)을 사용" => DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동하지만 모든 곳을 방문하기 때문에 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할 수도 있음. 따라서, 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈 수 있는 가능성이 있는 루트를 검사하는 방법이 백트래킹(Backtracking)알고리즘! # 백트래킹의 특징 : N이 작음(N이 10근처여야 사용가능함.) # => 재귀함수를 사용할 때, 종료 시점 잊지말기!!! 너비 우선 탐색(Breadth-First Search) : BFS 너비 우선 탐색(Breadth-First Search) - 그래프 탐색 방법 중 한 가지 종류 "시작 정점에 인접한 노드를 중심으로 탐색함" 아이디어 - 시작점에 연결된 Vertex 찾기 - 찾은 Vertex를 Queue에 저장 - Queue의 가장 먼저 것 뽑아서 반복 [그래프 예시] 파이썬으로 구현한 BFS 알고리즘 from collections import deque # BFS 함수 정의 def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 deque 라이브러리 사용 - 젤 처음에는 큐에 1만 들어가있음 queue = deque([start]) # 현재 노드를 방문 처리 visited[start] = True # 큐가 빌 때까지 반복 while queue: # 큐.. 이전 1 다음
