반응형 깊이 우선 탐색1 [알고리즘] DFS(Depth-First Search) - 깊이 우선 탐색 DFS는 그래프(Graph)를 탐색하는 방법입니다. 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조를 말합니다. 코딩 테스트에서 BFS와 단골로 나오는 개념입니다. DFS 깊이 우선 탐색(Depth-First Search) 정의 : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말합니다. 자기 자신을 호출하는 순환 알고리즘이기 때문에 재귀 함수나 스택을 가지고 구현합니다. 이때 주의 사항은 어떤 노드를 방문했었는지 여부를 반드시 검사해야 합니다. 📘 Pseudo Code /** 1. 노드이 갯수 만큼 방문 여부를 위한 배열 생성 후 false로 초기화 (visit 배열) 2. 루트 노드부.. 2021. 12. 1. 이전 1 다음 반응형
