DFS, BFS 개념 -(2)

DFS, BFS 개념 -(2)

7-6. 부분 집합 구하기 | DFS

• 전체 원소가 1~N까지인 집합의 부분집합
• 각 원소를 사용 O or 사용 X 각 2가지의 경우의 수 있다.

/* 7-6. 부분집합 구하기 DFS */
public class Main1 {
    //집합 원소의 개수  
    static int n;

    //각 원소 부분집합 사용 여부 체크 배열
    static int[] ch;

    //DFS 함수
    public void DFS(int L) {
        if(L == n+1) { // 단말 노드까지 찍으면 종료 
            String tmp = "";
            //전체 순회하면서 사용 체크된 원소만 String에 이어붙임
            for(int i = 1; i<= n; i++) {
                if(ch[i] == 1) tmp+= (i+ " ");
            }
            //공집합 제외 출력
            if(tmp.length()>0) System.out.println(tmp);
        }else {
            //각 원소에 대해서 재귀 호출
            //왼쪽 (사용O)
            ch[L] = 1; //사용O 체크
            DFS(L+1);
            //오르쪽 (사용X)
            ch[L] = 0; //사용x 체크 
            DFS(L+1);
        }
    }    

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        n = 3;
        ch = new int[n+1];
        T.DFS(1);
    }
}

---

7-7. 이진트리 순회(레벨 탐색) | BFS

import java.util.LinkedList;
import java.util.Queue;

/* 7-7. 이진트리 순회 (BFS : 레벨탐색)
 * */
class Node{
    int data;
    Node lt, rt;
    public Node(int val) {
        data = val;
        lt=rt= null;
    }
}
public class Main2 {
    Node root;
    public void BFS(Node root) {
        //큐 사용
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0; //레벨 
        while(!Q.isEmpty()) {
            int len = Q.size();
            System.out.print(L+" : ");
            //for()는 각 L에 대한 인ㅇ접 정점들 차례 방문 작업 함
            for(int i =0; i<len; i++) {
                //큐에서 하나 뽑고 
                Node cur = Q.poll();
                //현재 데이터 출력
                System.out.print(cur.data + " ");
                //만약 말단 노드만 아니면 , 
                //현제 데이터에 연결된 인접 정접들 모두
                // 차례로 큐에 담기 
                if(cur.lt != null) Q.offer(cur.lt);
                if(cur.rt != null) Q.offer(cur.rt);
            }
            //레벨 ++ 
            L++;
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 tree = new Main2();
        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);
        //BFS함수 호출
        tree.BFS(tree.root);
    }
}

---

7-8. 송아지 찾기 | BFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*7-8. 송아지 찾기 (BFS) 
[입력]
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 
직선의 좌표 점은 1부터 10,000까지이다.
[출력]
점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.*/
public class Main3 {
    //한 번의 점프 당 좌표 가능
    int[] dis = {1, -1, 5};
    //체크배열(방문여부)
    int[] ch;
    //큐
    Queue<Integer> Q = new LinkedList<>();
    //BFS 함수
    public int BFS(int s, int e) {
        ch=new int[10001]; // 1~10000 찍기 위함
        //들어온 루트 s 방문 처리
        ch[s] = 1;
        Q.offer(s);

        int L=0;  //레벨
        while(!Q.isEmpty()) {
            int len = Q.size();
            //각 레벨에 대한 작업
            for(int i=0; i<len; i++) {
                int x = Q.poll();//현재 대상 뽑고
                //목적지 e에 해당하는 원소인지 여기서 체크 후 
                if(x == e) return L;
                //아닌 경우, 다시 현 원소에 대한 3가지 점프 경우의 수(위치 dis)
                for(int j=0; j<3; j++) {
                    int nx = x + dis[j];//현 원소에서 가능한 각 좌표 더함
                    if(nx>=1 && nx<=10000 && ch[nx] == 0) {
                        // 좌표평번 내부의 값이면서, 방문 안한 nx 점에 대하여
                        //방문 처리
                        ch[nx] = 1;
                        Q.offer(nx); 
                    }
                }
            }
            //레벨++
            L++;
        }
        return 0;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb= new Scanner(System.in);
        int s = kb.nextInt();
        int e = kb.nextInt();
        //출력
        System.out.println(T.BFS(s, e));
    }
}

---

7-9. -(1) .Tree 말단 노드까지의 가장 짧은 경로(DFS)

/* 7-9. Tree 말단 노드까지의 가장 짧은 경로(DFS)*/
class Node1{ 
    int data; 
    Node1 lt, rt; 
    public Node1(int val) { 
        data=val; 
        lt=rt=null; 
    } 
} 
public class Main4 {
    Node1 root;
    public int DFS(int L, Node1 root) {
        //종료 조건 = 단말노드
        if(root.lt == null && root.rt == null) return L;
        else {
            return Math.min(DFS(L+1, root.lt),DFS(L+1,root.rt));
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main4 tree = new Main4();
        tree.root = new Node1(1);
        tree.root.lt = new Node1(2);
        tree.root.rt = new Node1(3);
        tree.root.lt.lt = new Node1(4);
        tree.root.lt.rt = new Node1(5);
        //출력
        System.out.println(tree.DFS(0, tree.root));
    }
}

---

7-9. -(2). Tree 말단 노드까지의 가장 짧은 경로(BFS)

• 최단거리 문제는 BFS로 푸는 것이 맞다.

import java.util.LinkedList;
import java.util.Queue;

/* 7-10. Tree 말단 노드까지의 가장 짧은 경로(BFS)*/

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

public class Main5 {
    Node2 root;

    public int BFS(Node2 root) {
        Queue<Node2> Q = new LinkedList<>();
        //방문
        Q.offer(root);
        int L = 0; //레벨 초기화

        while(!Q.isEmpty()) {
            int len = Q.size();
            for(int i=0; i<len; i++) {
                Node2 cur = Q.poll();
                //말단 노드인 경우 현재의 레벨 리턴
                if(cur.lt == null && cur.rt == null) return L;

                //왼쪾 자식 있는 경우
                if(cur.lt != null ) Q.offer(cur.lt);
                //오른쪽 자식 있는 경우
                if(cur.rt != null) Q.offer(cur.rt);
            }
            L++;
        }
        return 0;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main5 tree = new Main5();
        tree.root = new Node2(1);
        tree.root.lt = new Node2(2);
        tree.root.rt = new Node2(3);
        tree.root.lt.lt = new Node2(4);
        tree.root.lt.rt = new Node2(5);
        //출력
        System.out.println(tree.BFS(tree.root));
    }
}

---