[알고리즘] 깊이 우선 탐색 (DFS)

💡깊이 우선 탐색 (DFS)

• 그래프의 위에서 아래로 가장 깊은 곳을 방문하는 탐색법
• 한 방향으로 갈 수 있는데까지 가다가 길이 없으면 다시 돌아와 갈 수 있는데까지 가는 방법을 반복
• 어떤 노드를 방문 했었는지 검사 필요
• 스택 이나 재귀호출 방식을 사용해 구현 

 

✔️ 입력값 저장

• 인접리스트(링크드 리스트) 사용
• 인접 행렬 사용(2차원 행렬 사용)
• 큐 사용

1. 각 정점에 연결된 노드를 2차원 배열에 넣어준다. (양방향) ex. 1-2 이면 정점1에는 2를, 정점2에는 1을 넣어준다.

2. 만약 정점을 작은 순으로 탐색하고자 하면 오름차순으로 정렬해준다.

3. 탐색 시작 정점부터 탐색해 나가는데 시작 정점 배열의 size() 만큼 반복문을 돌린다. 

4. 한 정점을 탐색한 후 해당 정점에 인접한 방문하지 않은 노드가 있다면 재귀호출 방식으로 탐색한다.

5. 만약 모든 인접 노드가 탐색이 되었다면 재귀 호출했던 함수가 return 하면서 다시 돌아올거고, 남은 반복문을 돌면서 

    깊이 우선 탐색을 진행하게 된다.

 

✔️ 알고리즘 규칙(방문 규칙)

1. 시작 노드를 스택에 넣음

2. 인접한 노드 1개를 스택에 넣음(인접한 노드가 여러개면 통상 작은 노드 먼저), 인접한 노드가 없으면 스택에서 pop

3. 방금 넣은 노드에 또 인접한 노드를 넣음

3. 모든 정점을 방문하고 스택이 빌 때까지 반복

 

 

* 방문 처리와 탐색의 다른점 공부 필요

 

https://lotuslee.tistory.com/48

DFS(Depth First Search) - 깊이 우선 탐색

https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

DFS & BFS 이해하기 및 구현(C++)

 

* 스택에 인접한 노드를 모두 쌓는 방식으로 접근한 내용... 강사는 다양한 알고리즘이 있다는 식으로 말했는데 그냥 참고용으로만 활용....

https://velog.io/@falling_star3/2.-%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89DFS%EA%B3%BC-%EB%84%93%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS

[Algorithm] 깊이우선탐색(DFS)과 너비우선탐색(BFS)