[JAVA] 알고리즘 문제풀이 기초 - DFS, BFS - 기출문제

DFS, BFS 기출문제 풀이

바둑이 승차(DFS)

• 설명 : 철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.
  
  

• 입력 : 첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다. 둘째 줄부터 N마리 바둑이의 무게가 주어진다.
  
  

• 출력 : 첫 번째 줄에 가장 무거운 무게를 출력한다.
  
  

import java.util.*;

public class Main {

    static int wt, num, max=0;
    static int[] arr;

    public void DFS(int v, int sum){
        if(v>num || sum>wt) return;
        else if(max<sum) max=sum;

        if(v<num) {
            DFS(v+1, sum+arr[v+1]);
            DFS(v+1, sum);
        } else return;

    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        wt = scan.nextInt();
        num = scan.nextInt();
        arr = new int[num+1];
        for(int i=1; i<=num; i++){
            arr[i] = scan.nextInt();
        }
        main.DFS(0, arr[0]);
        System.out.println(max);
    }
}

• 정리
  
  • 처음엔 트리구조 만들 때 모든 배열을 한번씩 돌아서 노드로 만드는 것을 반복하려 했는데 그렇게 짜니까 아무리해도 비효율적이고 생각보다 코드 조건이 복잡해져서 풀이에 오래 걸림
    
  • 생각보다 많이 단순하게 chk 배열조차없이 이전처럼 합계 넣었을때와 안넣었을때만 구분하면 되는거였음