DFS, BFS

1. 합이 같은 부분집합

package com.codingtest.Algorithm.Chapter8.DFSBFS;

import java.util.Scanner;

public class 합이_같은_부분집합 {

    static String answer = "NO";
    static int len, total = 0;
    static boolean flag = false;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        len = in.nextInt();
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = in.nextInt();
            total += arr[i];
        }

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

    public static void DFS(int L, int sum, int[] arr) {
        if (flag) {
            return;
        }
        if (sum > total / 2) {
            return;
        }
        if (L == len) {
            if ((total - sum) == sum) {
                answer = "YES";
                flag = true;
            }
        } else {
            DFS(L + 1, sum + arr[L], arr);
            DFS(L + 1, sum, arr);
        }
    }
}

2. 바둑이 승차 _ 부분집합

부분집합

package com.codingtest.Algorithm.Chapter8.DFSBFS;

import java.util.Scanner;

public class 바둑이_승차 {

    static int totalWeight, num;
    static int[] dogs;
    static int answer = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        totalWeight = in.nextInt();
        num = in.nextInt();
        dogs = new int[num];
        for (int i = 0; i < num; i++) {
            dogs[i] = in.nextInt();
        }

        DFS(0, 0);

        System.out.println(answer);
    }

    public static void DFS(int idx, int sum) {

        if (sum > totalWeight) {
            return;
        }

        answer = Math.max(sum, answer);

        if (idx == num) {
            return;
        }
        
        DFS(idx + 1, sum);
        DFS(idx + 1, sum + dogs[idx]);

    }
}

OR

package com.codingtest.Algorithm.Chapter8.DFSBFS;

import java.util.Scanner;

public class 바둑이_승차 {

    static int totalWeight, num;
    static int[] dogs;
    static int answer = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        totalWeight = in.nextInt();
        num = in.nextInt();
        dogs = new int[num];
        for (int i = 0; i < num; i++) {
            dogs[i] = in.nextInt();
        }

        DFS(0, 0);

        System.out.println(answer);
    }

    public static void DFS(int idx, int sum) {

        if (sum > totalWeight) {
            return;
        }
        if (idx == num) {
            answer = Math.max(sum, answer);
        } else {
            DFS(idx + 1, sum);
            DFS(idx + 1, sum + dogs[idx]);
        }

    }
}

3. 최대점수 구하기 (DFS)

package com.codingtest.Algorithm.Chapter8.DFSBFS;

import java.util.ArrayList;
import java.util.Scanner;

public class 최대점수_구하기 {

    static int num, totalTime;
    static ArrayList<Question> arr = new ArrayList<>();
    static int maxScore = Integer.MIN_VALUE;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        num = in.nextInt();
        totalTime = in.nextInt();

        for (int i = 0; i < num; i++) {
            int score = in.nextInt();
            int time = in.nextInt();
            arr.add(i, new Question(score, time));
        }

        DFS(0, 0, 0);

        System.out.println(maxScore);
    }

    public static void DFS(int idx, int timeSum, int totalScore) {
        if (timeSum > totalTime) {
            return;
        }

        if (idx == num) {
            maxScore = Math.max(maxScore, totalScore);
        } else {
            DFS(idx + 1, timeSum, totalScore);
            DFS(idx + 1, timeSum + arr.get(idx).time,
                totalScore + arr.get(idx).score);

        }
    }

    public static class Question {

        public int score, time;

        Question(int score, int time) {
            this.score = score;
            this.time = time;
        }
    }
}

4. 동전 교환 _ 중복순열 구하기

package com.codingtest.Algorithm.Chapter8.DFSBFS;

import java.util.Scanner;

public class 동전교환 {

    static int coin, change;
    static int minChangeCnt = Integer.MAX_VALUE;
    static int[] arr;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        coin = in.nextInt();
        arr = new int[coin];
        for (int i = 0; i < coin; i++) {
            arr[i] = in.nextInt();
        }
        change = in.nextInt();

        DFS(0, 0, 0);

        System.out.println(minChangeCnt);
    }

    public static void DFS(int idx, int sum, int cnt) {
        if (sum > change) {
            return;
        }

        if (sum == change) {
            minChangeCnt = Math.min(minChangeCnt, cnt);
            return;
        }

        if (idx == coin) {
        } else {
            DFS(idx, sum + arr[idx], cnt + 1);
            DFS(idx + 1, sum + arr[idx], cnt + 1);
            DFS(idx + 1, sum, cnt);
        }
    }
}