Chapter 08. DFS, BFS 활용

1. 합이 같은 부분집합

java

열기 줄바꿈

import java.util.*;
public class Main {
  static String answer = "NO";
  static int n, total = 0;
  boolean flag = false;
  
  public void DFS(int L, int sum, int [] arr){
    if(flag == true) return;	//재귀가 바로 끝나도록한다.
    if(sum > total / 2) return;	// 확인할 필요가 없다.
    if(L == n){
    	if((total - sum) == sum){
    	answer = "YES";
      	flag = true;
    	}
    }
  	else{
    	DFS(L + 1, sum + arr[L], arr);
      	// 무조건  + 1, arr[L]을 sum에 누적
    	DFS(L + 1, sum, arr);
    }	
  }
  
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    int[] arr = new int[n];
    for(int i = 0;i < n; ++i){
    	arr[i] = in.nextInt();
      	total += arr[i];
    }
    T.DFS(0, 0, arr);
    System.out.println(answer);
    return ;
  }
}

  Note)

  - D(L, sum) :  L(level), sum(부분집합의 총합)

  - 부분집합은 하나만 구해서 전체 집합의 total에서 sum을 뺐을 때, sum이 되면 "YES"

  - boolean flag: yes가 발견되면 return 한다.

 

 

2. 바둑이 승차 - 최대한 많이 태우려고 한다.

java

열기 줄바꿈

import java.util.*;
public class Main {
  static int answer = Integer.MIN_VALUE, c, n;
 	public void DFS(int L, int sum, int[] arr){
    	if(sum > c) return;	
      	if(L == n) {	// sum이 c보다 크거나 같은 경우
        	answer = Math.max(answer, sum);	
        }else{
        	DFS(L + 1, sum + arr[L], arr);
        	DFS(L + 1, sum, arr);
        }
    }
  
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    c = in.nextInt();
    n = in.nextInt();
    int [] arr = new int[n];
    for(int i = 0; i < n; ++i){
    	arr[i] = in.nextInt();
    }
    T.DFS(0, 0, arr);
    System.out.println(answer);
    return ;
  }
}

  Note)

  - 부분집합이 트럭에 타는 바둑이들이라고 본다.

  - DFS(L, sum) : L() , sum(트럭에 타는 바둑이 무게)

 

 

3. 최대 점수 구하기

java

열기 줄바꿈

import java.util.*;
public class Main {
  
  static int answer = Integer.MIN_VALUE, n, m;

  // ps: problem score , pt: problem time
  public void DFS(int L, int sum, int time, int[]ps, int[] pt){
  	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){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    n = in.nextInt();	// 문제 개수
    m = in.nextInt();	// 제한 시간
    int [] a = new int[n];
    int [] b = new int[n];
    for(int i = 0; i < n; ++i){
    	a[i] = in.nextInt();	// 점수
      	b[i] = in.nextInt();	// 걸리는 시간
    }
    
    T.DFS(0, 0, 0, a, b);
    // int L, int sum, int time, int[]ps, int[] pt
    
    System.out.println(answer);
    return ;
  }
}

  Note)

  - N: 문제 개수, M: 제한 시간

  - D(L, sum , time, arr)

  - ps: problem score

  - pt: problem time

  - 시간과 점수를 모두 누적합 시킨다.

 

 

4. 중복 순열

java

열기 줄바꿈

package first;
import java.util.*;
public class Main {
  static int[]pm;
  static int n, m;
  public void DFS(int L){
  	if(L == m){
    	for(int x: pm) System.out.print(x + " ");
      	System.out.println();
    }else{
    	for(int i = 1; i <= n; ++i){
        	pm[L] = i;	// 상태트리로 스택 그려서 확인
          	DFS(L+1);
        }
    }
  }
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    m = in.nextInt();
   	pm = new int[m];
    T.DFS(0);
    return ;
  }
}

  Note) 실행 결과

 

 

5. 동전 교환

 

 

 

 

  Note) 실행 결과

  - DFS(L, sum)

  - L은 동전의 개수라고 생각한다.

  - sum은 L개의 동전의 총합으로 생각할 수 있다.

  -