바둑이 승차 문제 (DFS) - Java

기본적인 DFS문제를 풀어보았다.

설명

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.

철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.

N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.

둘째 줄부터 N마리 바둑이의 무게가 주어진다.

출력

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

 

예시입력

259 5
81
58
42
33
61

예시출력 : 242

위 예시입력처럼

넘으면 안되는 무게 : 259 // 입력받아 limit 변수에 담을 예정

int [] arr = {81, 58, 42, 33, 61}

가 주어지는데.

조건은 다음과 같다.

1. DFS로 arr 배열 요소들의 모든 조합에서 만들어지는 합을 구한다.

1-1. 단, limit (259)보다는 작아야 한다.

2.  1-1조건이 만족하면서 나오는 합 중 가장 큰 수를 출력한다.

 

- 소스코드

    메인 에서  DFS를 호출한다. 또한 매개변수는 시작점 v, 요소들의 합인 sum을 사용한다.

public void DFS(int v,int sum){...}

 

Main T = new Main();
T.DFS(0,0);

 

- 1-1에 합이 limit보다 작아야하기에 크면  else if(v==n) return 문으로 재귀를 빠져나온다.

 

- 무한루프를 방지하기 위해 . else if(v==n) 조건 사용 및 answer값 갱신

public void DFS(int v,int sum){
    if(sum>limit) return;
    else if(v==n) {
        answer = Math.max(sum,answer);
    }
    else{
        DFS(v+1,sum+arr[v]); // Line 14
        DFS(v+1,sum); // Line 15
    }
}

 

- 위 경우들이 아니면 DFS 탐색.

else{
        DFS(v+1,sum+arr[v]); // Line 14
        DFS(v+1,sum); // Line 15
    }

 

간략하게 생략했지만  그림으로 표현하면 DFS의 매개변수는 이런식으로 동작한다.

 

 

-문제출처 : 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 김태원