문제 1.
해결방법
- 각 원소를 포함한다(O) 포함하지 않는다. (X)로 구현 -> DFS
- 종료조건은 level이 끝까지 다 다를때까지이다.
(종료 조건이 헷갈릴경우에는 n이 1개라고 생각하고 접근하기 ) - 이 문제는 check배열을 사용하지 않는다. 이유는 포함한다, 포함하지 않는다로 모든 조건을 검색하기 때문에
조심해야 할 점
- 종료조건 잘 살피기
- hap을 넘길때는 hap+=arr[l+1]이 아닌 hap+arr[l+1]이다. 이미 hap은 누적값이기 때문에
- 종료조건의 (sum-hap)==hap으로 지금까지 더한 합이 나머지 합과 같다면 종료
코드
package inflearn.section8_dfs_bfs활용;
// 합이 같은 부분집합
// dfs
// 포함한다 안한다로 넓힘
// 1 3 5 6 7 10 -> 여기선 10까지 다 들어가는것을 의미
// 끝나는 조건은 언제까지? -> level이 다 다르면 끝, level은
// 입력 값
// 6 (개수)
// 1 3 5 6 7 10
import java.util.*;
public class 합이같은부분집합 {
static int n;
static int arr[]; // 해당 노드 방문 여부는 필요 없음. -> OX로 나누는 것이기 때문에 나누어짐
static String answer="NO";
static int sum;
static boolean flag=false;
public void dfs(int l, int hap) {
if (flag) return;
if (l==n) { // 헷갈리면 1개만 사용할때를 생각해보자
if ((sum-hap)==hap) { // 전체 토탈에서 빼준다. /2로 하면 합이 125같은 홀수 일때 문제, 125/2==62가 되어버림
answer="YES";
flag=true;
}
}
else {
// 사용한다
dfs(l+1,hap+arr[l+1]); //여기가 잘못, 누적하면 안됨, hap은 이미 누적되어 있는 값임
dfs(l+1,hap);// 사용안한다
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
sum=0;
arr=new int [n+1];
for (int i=1;i<=n;i++) {
int k=scan.nextInt();
sum+=k;
arr[i]=k;
}
// System.out.println(sum);
// 절반으로 나눈값으로 같아지면 됨
// 16으로 맞추면 됨
합이같은부분집합 test=new 합이같은부분집합();
test.dfs(0,0);
System.out.println(answer);
// ArrayList<Integer> arrayList=new ArrayList<>();
}
}
문제 2
- 위 부분집합의 합과 거의 비슷한 문제, 있다 없다. (OX)의 DFS로 문제 풀이
주의할 점
- 만약 구할려는 값보다 합이 크면 return으로 빨리 종료하기
코드
package inflearn.section8_dfs_bfs활용;
import java.util.*;
public class 바둑이승차 {
static int sum;
static int arr[];
static int total;
static int n;
public void dfs(int l, int hap) {
if (hap>total) return; // 이 조건을 추가해야지 빨라짐
if (l==n) {
if (hap<=total) {
if (hap>sum) {
sum=hap;
}
}
}
else {
// 바둑이를 태운다
dfs(l+1,hap+arr[l+1]);
// 바둑이를 태우지 않는다.
dfs(l+1,hap);
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
total=scan.nextInt();
n=scan.nextInt();
arr=new int[n+1];
for (int i=1;i<=n;i++) {
arr[i]=scan.nextInt();
}
바둑이승차 m1=new 바둑이승차();
m1.dfs(0,0);
System.out.println(sum);
}
}
문제 3.
해결방법
- 위 1,2문제와 비슷 (문제를 푼다 안푼다로 구분하면 됨)
- 단 time이 추가되었기 때문에 time배열과 scores배열을 만들자
- Math.max를 이용해서 최대 점수를 갱신하자
코드
package inflearn.section8_dfs_bfs활용;
import java.util.*;
public class 최대점수구하기 {
static int score[];
static int time[];
static int n;
static int m;
static int hap;
void dfs(int l, int ts, int tt) {
if (tt>m) {
return;
}
if (l==n) {
hap=Math.max(ts,hap);
}
else {
// 문제 푼다
dfs(l+1,ts+score[l+1],tt+time[l+1]);
// 문제 안푼다.
dfs(l+1,ts,tt);
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
score=new int[n+1];
time=new int[n+1];
for (int i=1;i<=n;i++) {
int sc=scan.nextInt();
int tt=scan.nextInt();
score[i]=sc;
time[i]=tt;
}
최대점수구하기 m1=new 최대점수구하기();
m1.dfs(0,0,0);
System.out.println(hap);
}
}
문제 3. DFS로 중복순열 구하기
해결방법
- DFS가 0일때 어떻게 뻗어나가는지 구하기
- 중복 순열은 1~N까지 뻗어나감
- 배열은 m개 만큼 만들기
- if 종료 조건은 level이 m에 도달하였을때 종료 후 ch배열에 있는거 출력
- else 조건은 1~N만큼 for문을 돌면서 ch배열에 i를 넣고 dfs를 돌린다.
코드
package inflearn.section8_dfs_bfs활용;
import java.util.*;
public class 중복순열구하기 {
static int arr[];
static int n;
static int m;
public void dfs(int l) {
// 종료
if (l==m) {
String temp="";
for (int i=0;i<m;i++) {
temp+=arr[i]+" ";
}
System.out.println(temp);
}
else {
for (int i=1;i<=n;i++) {
arr[l]=i;
dfs(l+1);
}
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m= scan.nextInt();
arr=new int[m];
중복순열구하기 m1=new 중복순열구하기();
m1.dfs(0);
}
}
문제 4. 동전교환
해결방법
- 가지치기로 뻗어나가서 m가 같을때까지 뻗어나간다
- 만약 m보다 값이 커지면 종료 return
- 같으면 return -> Math.min(count,l) -> l이 의미하는것은 사용개수를 의미함.
- 그렇지 않으면 더 가지치기 for문으로
- 시간을 더 줄일 수 있는 방법은?
1. 이미 구한 답 count보다 l이 더 깊게 들어갈 경우 종료
2. 동전을 내림차순으로 정렬하기
- 주의점은 배열을 내림차순할때는 Integer를 사용한다.
- Arrays.sort(arr,Collections.reverseOrder());
코드
package inflearn.section8_dfs_bfs활용;
import java.util.*;
public class 동전교환 {
static int n;
static Integer arr[];
static int change;
static int count=Integer.MAX_VALUE;
public void dfs(int l, int hap) {
// time Limit이 일어남 -> 가지치기 해서 시간을 줄일수있는 방법을 생각해보자
// 이 조건도 넣을수 있지 않을까? 이미 앞에서 l이 나왔는데 더 들어갈 필요가 없으면 종료
// 가지치기해야 할 것을 생각해본다.
if (count<l) {
return;
}
// 더 줄일수 있지 않을까?!
if (hap>change) {
return;
}
else if(hap==change) {
count=Math.min(count,l);
}
else {
for (int i=0;i<n;i++) {
dfs(l+1,hap+arr[i]);
}
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
arr=new Integer[n];
for (int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
change=scan.nextInt();
// 내림차순 정렬
// 배열은 내림차순 하려면 Integer로 변경해야 한다.
//
Arrays.sort(arr,Collections.reverseOrder());
동전교환 m1=new 동전교환();
m1.dfs(0,0);
System.out.println(count);
}
}
BackEnd Developer