[인프런 자바/java] 2. 바둑이 승차(DFS) _디버깅의 눈물

체크 포인트

 

1. DFS(깊이 우선 탐색)을 이용하는 문제

-철수가 트럭에 태울 수 있는 '강아지 총 무게의 합'을 구하는 문제

-몸무게 합 259kg을 넘지 않으면서 태울 수 있는 '최대 무게의 합'을 구해야 한다.

-이를 위해 모든 강아지를 (1)태우거나 (2)태우지 않거나의 경우로 나누어 모두 탐색해야 한다.

 

2. 강아지를 트럭에 태우는 것과 안 태우는 것을 어떻게 표현할지 고민했다.

-첫번째 강아지를 트럭에 태우는 경우/태우지 않는 경우

-두번째 강아지를 트럭에 태우는 경우/태우지 않는 경우

...

-N번째 강아지를 트럭에 태우는 경우/태우지 않는 경우

 

특정 강아지를 트럭에 태우는 것/안 태우는 것을 구현하기 위해,

 

		// 해당 숫자를 합한 경우,
        	DFS(x+1, sum+map[x]);
        	// 해당 숫자를 합하지 않은 경우,
        	DFS(x+1, sum);

 

해당 강아지의 몸무게를 추가한 후 DFS탐색을 하는 경우/몸무게를 추가하지 않고 DFS탐색을 하는 경우로 분류했다.

 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	
	// 철수가 트럭에 태울 수 있는 가장 무거운 무게
	static int C;
	
	// 강아지 마리 수 
	static int N;
	
	// 강아지 무게의 합
	static int sum;
	
	// 강아지 합 최댓값
	static int max;
	
	// 강아지 몸무게 배열
	static int[] map;

	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	
    	// 철수가 트럭에 태울 수 있는 강아지 총 무게 합 제한 
    	C = Integer.parseInt(st.nextToken());
    	// 강아지 총 마리수 
    	N = Integer.parseInt(st.nextToken());
    	
    	// 강아지 몸무게 배열 
    	map = new int[N];
    	
    	// 강아지 몸무게 배열 입력 
    	for(int i=0; i<N; i++) {
    		map[i] = Integer.parseInt(br.readLine());
    	}
    	
    	
    	/*
    	for(int i=0; i<N; i++) {
    		System.out.println(map[i]);
    	}
    	*/
    	
    	// 몸무게 합 최대값 초기화 
    	max = Integer.MIN_VALUE;
    	
    	// 배열에서 0번째 강아지부터 탐색 시작 
    	DFS(0, 0);
    	
    	System.out.println(max);
    }
    
    static void DFS(int x, int sum) {
    	
    	// 현재 강아지 총 몸무게의 합이 총 몸무게 제한보다 큰 경우,
    	// return 
    	if(sum>C) {
    		return;
    	}
    	
    	if(sum>max) {
    		// 현재 강아지 총 몸무게의 합이 기존의 몸무게 합보다 큰 경우,
    		// 최대값을 sum으로 변경 
    		max = sum;
    	}
    	
    	// 해당 강아지가 마지막 강아지가 아니라면,
    	if(x!=N) {
        	
    		// 해당 숫자를 합한 경우,
        	DFS(x+1, sum+map[x]);
        	// 해당 숫자를 합하지 않은 경우,
        	DFS(x+1, sum);
    	}
    	
    	
    	
    }
    

} // end of Main