깊이 우선 탐색(DFS)

깊이 우선 탐색이란?

---

깊이 우선 탐색(Depth-First Search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. 일반적으로 재귀호출을 이용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다.

이미지 출처 : 위키백과

 

장점과 단점

---

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

 

 

DFS 예제

---

https://school.programmers.co.kr/learn/courses/30/lessons/43165

 

 

public class TargetNumber {
    // https://school.programmers.co.kr/learn/courses/30/lessons/43165
    // 타겟 넘버
    int[] numbers;
    int target;
    int answer;

    public int solution(int[] numbers, int target) {
        answer = 0;
        this.numbers = numbers;
        this.target = target;

        dfs(0, 0);

        return answer;
    }

    public void dfs(int index, int sum) {
        if (index == numbers.length) {
            if (sum == target) {
                answer++;
            }
            return;
        }
        dfs(index + 1, sum + numbers[index]);
        dfs(index + 1, sum - numbers[index]);
    }
}

배열 [1,1,1]이 주어졌을 경우

 

최초로 주어지는 값 0을 기준으로 부모노드로 설정하고 조건에 따라 자식노드를 생성하여서 최종적으로 8개의 값이 나옵니다. 노드 생성 순서는 위키백과에서 제공하는 GIF와 동일하게 생성됩니다. 

 

 

 

 

출처 : https://www.youtube.com/watch?v=S2JDw9oNNDk&t=151s,

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89