DFS, BFS 활용 섹션 - (1)

📍 섹션8. DFS, BFS 활용

DFS, BFS 활용 섹션 - (1)

8-1. 합이 같은 부분집합 | DFS

import java.util.Scanner;

/* 8-1. 합이 같은 부분집합 (DFS)
[입력]
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.
[출력]
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.*/
public class Main1 {
    static String answer = "NO";
    static int n, total=0;
    boolean flag = false;

    //DFS
    public void DFS(int L, int sum, int[]arr) {
        if(flag == true) return;
        if(L == n) { //레벨이 n렙벨 되면 하나의 부분집합 깊이 탐색 완료된 시점임
            if(total - sum == sum) {
                answer = "YES";
                flag = true;
            }
        }else {
            //왼쪽 사용 O
            DFS(L+1, arr[L]+sum, arr);
            //오른쪽 사용 X
            DFS(L+1, sum, arr);
        }
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb =new Scanner(System.in);
        n= kb.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = kb.nextInt();
            total += arr[i];
        }
        T.DFS(0, 0, arr);
        System.out.println(answer);
    }    
}

---

8-2. 바둑이 승차 | DFS

import java.util.Scanner;

/* 8-2. 바둑이 승차(DFS)
[입력]
첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.
둘째 줄부터 N마리 바둑이의 무게가 주어진다.
[출력]
*/
public class Main2 {
    static int c, n, answer=Integer.MIN_VALUE;
    boolean flag = false;
    //DFS
    public void DFS(int L, int sum, int[]arr ) {
        //트럭 용량 C 넘어가면 그냥 리턴
        if(sum > c) return;
        if(L == n) {
            //마지막 레벨딴 까지 오면 기존 answer와 들어온 sum 중에 더 큰 값으로 answer 세팅
            answer = Math.max(answer, sum);
        }else {
            //사용O
            DFS(L+1, sum+arr[L], arr);
            //사용X
            DFS(L+1, sum, arr);
        }
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);
        c = kb.nextInt();
        n = kb.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) arr[i] = kb.nextInt();

        T.DFS(0, 0, arr);
        System.out.println(answer);
    }
}

---

8-3. 최대 점수 구하기 | DFS

import java.util.Scanner;

/* 8-3. 최대 점수 구하기 DFS  
 * */
public class Main3 {
    static int answer = Integer.MIN_VALUE;
    static int n, m;
    boolean flag = false;
    //DFS
    public void DFS(int L, int sum, int time, int[]ps, int[]pt) {
        //제한 시간 넘어갈 경우 return;
        if(time > m) return;
        if(L == n) {
            answer = Math.max(answer, sum);
        }else {
            //문제 푼다
            DFS(L+1, sum+ps[L], time+pt[L], ps, pt);
            //문제 안푼다.
            DFS(L+1, sum, time, ps, pt);
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt(); //문제수
        m = kb.nextInt(); //제한 시간 
        int[] ps = new int[n];
        int[] pt = new int[n];
        //입력받기 
        for(int i=0; i<n; i++) {
            ps[i] = kb.nextInt();
            pt[i] = kb.nextInt();
        }
        T.DFS(0, 0, 0, ps, pt);
        //출력
        System.out.println(answer);
    }
}

---

8-4. 중복 순열 구하기 | DFS

• 이 문제는 1~N까지 중복 허용하여 M번 뽑아 일렬로 나열하라고 한다.
• 레벨 L은 M번까지 깊이 들어갈 수 있고, M번을 다 뽑았으면 스택 back 하면 됨
• 각 레벨 L에서는 for(int I~N)까지 돌면서
• **각 L번쨰 뽑았을 때 pm[L] = I 담고, DFS(L+1) 로 뻗어나간다.**

import java.util.Scanner;

/* 8-4. 중복순열 구하기*/
public class Main4 {
    static int[] pm; 
    static int n, m;
    //DFS  n개씩 뻗어나가면서 m번 뽑아나감  
    public void DFS(int L) {

        if(L == m) { //정해진만큼 뽑았으면 깊이 O
            for(int x : pm) System.out.print(x+ " ");
            System.out.println();

        }else {
            //각 단계에서 1~n가닥씩 뻗어나감 
            for(int i=1; i<=n; i++) {
                pm[L] = i;//중복순열 담고 
                DFS(L+1);
            }
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main4 T = new Main4();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        pm = new int[m]; //m번 뽑으니까

        T.DFS(0);
    }
}

---