[JAVA] 알고리즘 문제풀이 기초 - DFS

DFS (깊이 우선 탐색)

기초 구현

import java.util.*;

class Node {
    int data;
    Node lt, rt;
    public Node(int val) {
        data = val;
        lt=rt=null;
    }
}

public class Main {

    Node root;
    public void DFS(Node root){
        if(root==null) return;

        // System.out.print(root.data+" "); 전위순회
        DFS(root.lt);
        // System.out.print(root.data+" "); 중위순회
        DFS(root.rt);
        // System.out.print(root.data+" "); 후위순회
    }

    public static void main(String[] args) {
        Main tree = new Main();
        tree.root=new Node(1);
        tree.root.lt=new Node(2);
        tree.root.rt=new Node(3);
        tree.root.lt.lt=new Node(4);
        tree.root.lt.rt=new Node(5);
        tree.root.rt.lt=new Node(6);
        tree.root.rt.rt=new Node(7);
        tree.DFS(tree.root);
    }
}

정리
1. 문제 풀이하기 전 DFS 기본 구조를 작성 해봄

### 원소 집합 구하기 (DFS)

문제 : 1부터 지정된 숫자의 부분집합의 경우의 수를 모두 구하여라
구현 ``` import java.util.*;

public class Main { static int num; static int[] chk; public void DFS(int val){ if(val==num+1){ for(int i=0; i<val; i++){ if(chk[i]==1) System.out.print(i+” “); } System.out.println(); } else { chk[val]=1; DFS(val+1); chk[val]=0; DFS(val+1); } }

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    num = scan.nextInt();
    chk = new int[num+1];

    Main main = new Main();
    main.DFS(1);
} } ```

정리
1. 트리구조를 만들어 해당 원소를 포함할지, 안할지 분리
2. 이때 출력여부를 chk라는 배열에 저장함
3. 체크를 마치면 +1을 해서 다음숫자를 계속해서 포함O, 포함X 트리로 뻗어나감
4. 계속 +1을 해가다가 지정숫자보다 큰 수가 나오면 트리생성을 마치고
5. chk 배열에 1이 담긴것만 출력

IM

DFS (깊이 우선 탐색)