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);
}
}
}
Last updated