DFS

그래프 탐색의 방법

참고) BFS

스택, 재귀함수

재귀함수

자기 자신을 다시 호출하는 함수

• 주의할 점
  - 재귀함수 깊이가 너무 깊어지면 stack overflow => 재귀함수가 종료되는 시점 반드시 명시
• DFS, 백트랙킹에 주로 사용

아이디어

1. 시작점에 연결된 Vertex 찾기
2. 연결된 Vertex를 계속해서 찾음 (끝날 때까지)
3. 더 이상 연결된 Vertex가 없을 경우 다음

시간 복잡도

DFS: O(V+E) => Vertex 개수 + Edge의 개수

1 > a > 2 > d > 3 > e > 4 > g > 6 > b > 5 > f

자료구조

1. 검색할 그래프: 2차원 배열
2. 방문여부 확인: 2차원 배열(재방문 금지)