DFS(깊이 우선 탐색)

깊이 우선 탐색이란

한곳만 파고, 없으면, 다시 한곳만 파는 방식의 탐색이다.

주로, 어떠한 노드와 여러 갈림길이 있을 때, 어떤 길이 가장 길고, 짧은지를 알 고 싶을 때, 사용한다.

 

DFS의 요소로는 

1. 노드에 미리 왔다 감을 표현하는

boolean 배열

2. 노드와 노드를 이어주는 앳지

3. 노드

이렇게 3개가 있다.

 

그림으로 설명해본다.

 

<후에 추가>

 

 

dfs는 주로 재귀함수로 표현이 될 수 있다.

dfs(int value){

1. 왔다 갔나? (조건)

-> yes일 시 return

->no일 시(아직 안와봄) boolean 배열에 true 추가, 연결 리스트의 다음 노드 확인

2. 다음 노드에 dfs 즉, dfs(다음 노드) => 재귀함수

3. 모든 연결리스트를 확인하면 이 dfs는 끝남

}

이런식이다.