알고리즘/알고리즘 개념
[알고리즘] 깊이 우선 탐색 (depth-first search, DFS)
깊이 우선 탐색(depth-first search, DFS) ① 깊이 우선 탐색이란? ▷ 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법▷ 깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않습니다.▷ 깊이 우선 탐색의 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 돌아간다는 점입니다.▶ 깊이 우선 탐색 구현할 경우 : 스택(Stack)의 성질 활용(방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 형태로 구현) ※ DFS : 스택(Stack), BFS : 큐(Queue) 를 사용합니다.▶ 알고리즘 해결할 경우 : '재귀 호출'을 이용해 해결 (재귀 호출한 함수가 종료하면 호출한..
2018. 4. 12. 13:47