DFS

여태 열심히 알고리즘들을 풀었으니    
본격적으로 DFS와 BFS를 풀어야 할 때가 됐다.

2023년 12월 15일 TIL

DFS

Depth First Search

원론적인 개념

1. 깊이 우선탐색 혹은 깊이 탐색 혹은 dfs 로 불리는 탐색 방법이다.

2. 트리같은 자료구조에서 사용되며, Stack<> 과 재귀 를 사용하여 모든 분기를 방문한다.

3. (특정 노드, 보통은 트리의 꼭대기 에서 출발하는) 시작 노드로부터 인접해있는 노드들을 방문하며, 더 이상 방문할 노드가 없다면 백트래킹 하여 가장 상위 노드에서 접근 가능한 노드가 있는지 체크한다.

4. 모든 노드를 방문하거나, 특정 조건을 만족하는 노드를 찾으면 종료한다.
   (이 때, 특정 조건을 만족하는 노드를 찾는 조건은 BFS 와 DFS 중 상황에 맞는 적합한 탐색 방법을 고려해본다.)

보통 DFS 를 미로탐색 BFS 를 최단거리탐색 으로 설명한다.

사실 여기 저기를 찾아봐도 사실 글 설명만 봐서는 이해가 잘 되지 않았다.
직접 쉬운 DFS 문제들을 풀며 이해해보기로 했다.

타겟넘버

타겟 넘버

타겟넘버

    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }

기본적으로 재귀를 이용하여 시작되며

    private int dfs(int[] numbers, int target, int index, int currentSum) {
        if (index == numbers.length) {
            if (currentSum == target) {
                return 1;
            } else {
                return 0;
            }
        }



        int result = 0;
        result += dfs(numbers, target, index + 1, currentSum + numbers[index]);
        result += dfs(numbers, target, index + 1, currentSum - numbers[index]); 
        return result;
    }

이 문제의 재귀는 두 파트로 나뉜다.

노드의 끝에 도달했을 때

   if (index == numbers.length)

해당 노드 끝의 값이 목표와 같은지

    if (currentSum == target)
          return 1;
    else
          return 0;

그리고, 아직 진행 할 노드가 남았다면

    int result = 0;
    result += dfs(numbers, target, index + 1, currentSum + numbers[index]);
    result += dfs(numbers, target, index + 1, currentSum - numbers[index]); 
    return result;

재귀 조건을 들어가게 된다.

피로도 ( 업데이트 해야함 )

피로도

피로도

    public static int solution(int k, int[][] dungeons) {
        maxDungeonsExplored = 0;  // 최대로 탐험할 수 있는 던전 수 초기화
        boolean[] visited = new boolean[dungeons.length];  // 각 던전 방문 여부를 추적
        exploreDungeons(k, dungeons, visited, 0);  // 던전 탐색 시작
        return maxDungeonsExplored;  // 최대 탐험 가능한 던전 수 반환
    }

  private static void exploreDungeons(int fatigue, int[][] dungeons, boolean[] visited, int count) {
        for (int i = 0; i < dungeons.length; i++) {
            // 아직 방문하지 않은 던전이고, 피로도가 충분한 경우
            if (!visited[i] && fatigue >= dungeons[i][0]) {
                visited[i] = true;  // 던전 방문 처리
                exploreDungeons(fatigue - dungeons[i][1], dungeons, visited, count + 1);  // 다음 던전 탐색
                visited[i] = false;  // 탐색 후 던전 방문 처리 해제
            }
        }
        maxDungeonsExplored = Math.max(maxDungeonsExplored, count);  // 최대 탐험 가능한 던전 수 갱신
    }

풀이 공식