DFS (Depth First Search)

DFS
Depth First Search
깊이 우선 탐색
완전 탐색
시작점에서 갈수 있는 정점부터 깊이 있게 파고 드는 알고리즘
현재 정점과 연결된 정점들을 하나씩 갈 수 있는지 검사하고, 특정 정점으로 갈 수 있다면 그 정점에 가서 같은 행위를 반복한다. 이때, 방문한 지점은 다시 방문하지 않기 위해 표시를 해둔다.
활용: 전수 조사 (Brute Force, 다 해보기)
트리를 모두 순회할 때 사용한다.
현재 정점에서 한 방향으로 가면서 검사하기.
이전에 갔던 노드로 다시 올라간다. → Stack과 비슷하다.
Stack으로 구현
컴퓨터 메모리는 Stack으로 관리한다. → 재귀함수를 하면 자동적으로 Stack이 된다.
코딩테스트에서 중요하다.
모든 걸 다 찾아봐야 할 때는 DFS를 사용한다.