깊이 우선 검색 DFS도문 상해Java 코드leetcode 문제 풀이 템 플 릿

8098 단어 #BFS&DFS데이터 구조 와 알고리즘
깊이 우선 검색 DFS도문 상해Java 코드leetcode 문제 풀이 템 플 릿
  • 1. 참조 링크
  • 2. 그림 설명
  • 3. 총화
    • 참조 링크
    - 주 본 고 는 개인 학습, 권리 침해 삭제 에 만 사용 된다.
  • 1. 기초 설명
  • 검색 사상 - DFS & BFS (기초 편)
  • 데이터 구조: 그림 의 옮 겨 다 니 기 - 깊이 우선, 너비 우선
  • 2. 세트 템 플 릿
  • ① 깊이 우선 검색 템 플 릿 (LeetCode)
  • DFS 를 실현 하 는 방법 은 두 가지 가 있다.첫 번 째 방법 은 재 귀 를 하 는 것 이다. 이 점 은 이미 잘 알 고 있 을 것 이다.여기 서 우 리 는 참고 로 템 플 릿 을 제공 했다.
  • 우리 가 DFS 를 재 귀적 으로 실현 할 때 어떤 스 택 도 사용 할 필요 가 없 을 것 같다.그러나 실제로 우리 가 사용 하 는 것 은 시스템 이 제공 하 는 암시 적 스 택 이 고 호출 스 택 (Call Stack) 이 라 고도 부른다.
  • DFS - 템 플 릿 I 
    /*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}
  • 재 귀적 해결 방안 의 장점 은 그것 이 더욱 쉽게 실현 된다 는 것 이다.그러나 재 귀 깊이 가 너무 높 으 면 스 택 이 넘 치 는 단점 이 있다.이 경우 BFS 를 사용 하거나 명시 적 스 택 을 사용 하여 DFS 를 실현 하 기 를 원 할 수 있 습 니 다.
  • DFS - 템 플 릿 II 
    /*
 * Return true if there is a path from cur to target.
 */
 boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> s;
    add root to s;
    while (s is not empty) {
        Node cur = the top element in s;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to s;
                add next to visited;
            }
        }
        remove cur from s;
    }
    return false;
}
  • ② 역 추적 알고리즘 문제 풀이 세트 프레임 워 크 (labuladong 의 알고리즘 커닝): 상세 한 내용 은 2 절
    • 참조.

    그림 설명
  • 역 추적 알고리즘 문제 풀이 세트 프레임 워 크
  • DFS 알고리즘 은 바로 역 추적 알고리즘 으로 쓸데없는 말 을 하지 않 고 바로 역 추적 알고리즘 구조 에 올 라 갑 니 다.역 추적 문 제 를 해결 하 는 것 은 사실상 결정 트 리 의 역력 과정 이다.너 는 세 가지 문제 만 생각해 야 한다.
  • 1. 경로: 즉, 이미 한 선택 이다.
  • 2. 선택 목록: 즉, 당신 이 현재 할 수 있 는 선택 입 니 다.
  • 3. 종료 조건: 즉, 결정 나무 밑 에 도착 하여 더 이상 선택 할 수 없 는 조건 이다.

  • 역 추적 알고리즘 프레임 워 크 
    result = []
def backtrack(  ,     ):
    if       :
        result.add(  )
        return

    for    in     :
           
        backtrack(  ,     )
  • 그 핵심 은 바로 for 순환 안의 재 귀 입 니 다. 재 귀 호출 전에 '선택' 을 하고 재 귀 호출 후에 '선택 취소' 를 하 는 것 입 니 다. 특히 간단 합 니 다.


    • 3. 총화
  • 역 추적 알고리즘 은 다 진 트 리 의 옮 겨 다 니 는 문제 이다. 관건 은 바로 앞 순서 와 뒤 순서 가 옮 겨 다 니 는 위치 에서 조작 하 는 것 이다. 알고리즘 구 조 는 다음 과 같다. 
    def backtrack(...):
    for    in     :
           
        backtrack(...)
  • backtrack 함 수 를 쓸 때 지나 간 '경로' 와 현재 할 수 있 는 '선택 목록' 을 유지 해 야 합 니 다. '종료 조건' 이 실 행 될 때 '경로' 를 결과 집합 에 기록 해 야 합 니 다.
  • 사실 생각해 보면 역 추적 알고리즘 과 동적 계획 이 비슷 하지 않 을까요?우 리 는 동적 기획 시리즈 글 에서 동적 기획 의 세 가지 명확 한 점 이 바로 '상태', '선택' 과 'base case' 라 고 여러 번 강조 했다. 지나 간 '경로', 현재 의 '선택 목록' 과 '끝 조건' 에 대응 하 는 것 이 아 닐 까?
  • 어느 정도 에 말 하면 * * 동적 계획 의 폭력 구 해 단 계 는 바로 역 추적 알고리즘 이다. * *다만 일부 문 제 는 중첩 자 문제 성격 을 가지 고 dp table 또는 비망록 으로 최적화 시 켜 재 귀 나 무 를 대폭 자 르 면 동적 계획 이 된다.오늘 의 두 가지 문 제 는 모두 중첩 자 문제 가 없다. 즉, 역 추적 알고리즘 문제 이 고 복잡 도가 매우 높 은 것 은 불가피 하 다.
    • Weblogic-WebServer.Apache
    우 객 이 문 제 를 푸 는 것 은 배열 을 가장 작은 수로 배열 하 는 것 이다.

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage