DFS란 무엇인가

DFS

• 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 입니다.
• 그림에서 보이듯 시작노드를 방문하고 연결된 다음 노드에 방문, 그 다음 연결된 노드에 방문...
• 그러다 (연결이 안되어있으면) or (모두 방문한 노드라면) 이전 노드로 이동 후 연결된 노드(방문이 안된 노드)에 대해 다시 DFS를 수행합니다.

DFS 동작과정

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다.
2. (1) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 -> 인접 노드를 스택에 넣고, 방문처리 한다.
3. (2) 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
4. 2번의 과정을 수행할 수 없을 때까지 반복한다.

!https://workat.tech/images/ps/dfs-of-acyclic-graph.svg

프로그래머스 예제 : 87946

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

private static void dfs(int[][] dungeons, int[] visited, int k, int count){
    for(int i = 0; i < dungeons.length; i++){
        if(visited[i] == 0 && k >= dungeons[i][0]){
            visited[i] = 1;
            dfs(dungeons, visited, k - dungeons[i][1], count + 1);
            visited[i] = 0;
        }
    }

    if(amswer < count){
        amswer = count;
    }
}

1. dungeons를 순회하며 던전을 탐험
2. 각 던전이 아직 방문하지 X && 현재 피로도K가 던전을 탐험하기에 충분하면 (visited[i] == 0 && k ≥ dungeons[i][0]) 해당 던전을 탐험한다
   1) 탐험을 완료 했다면 visited를 업데이트 한다 visted[i] == 0
   2) 남은 피로도(k - dungeon[i][1]) 업데이트
   3) 탐험 횟수 (count + 1)
3. 업데이트 된 탐험 횟수를 인자로 가지고 다시 dfs메소드를 호출
4. 모든 던전을 탐험 했다면 answer값과 탐험 횟수(count)를 비교하여 더 높은 값을 넣어준다

프로그래머스 예제 : 43165
https://school.programmers.co.kr/learn/courses/30/lessons/43165

public static void dfs(int[] numbers, int depth, int target, int result) {
    if (depth == numbers.length) {
        if (target == result) {
            count++;
        }
        return;
    }

    int plus = result + numbers[depth];
    int minus = result - numbers[depth];

    dfs(numbers, depth+1, target, plus);
    dfs(numbers, depth+1, target, minus);
}

1. 재귀의 탈출 조건은 시행횟수(depth : numbers의 인덱스값)가 numbers의 길이만큼 커졌을 때(모든 numbers를 처리했을 때)
   1) 타겟 넘버(target)를 충족하면 경우의 수 (count) 증가하고
   2) 모든 numbers를 처리 했으니 return으로 탈출
2. 탈출 조건을 만족하지 않을때 (아직 다 탐색하지 않음)
   1) 모든 number를 돌면서 plus 혹은 minus된 인자값을 가지고 재귀 호출하며 탐색
   2) 모든 배열을 돌며 target에 도달하는 경우의 수를 찾아 탈출