섹션 8. DFS, BFS 활용 2. 바둑이 승차(DFS)

문제

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

입력

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

출력

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

입출력 예제

---

풀이방식

재귀함수란 자기가 자기 자신을 호출하는 함수이며, 스택 프레임을 사용한다.

---

재귀함수에 대한 자세한 설명은 아래 글을 참조하길 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)

---

설계과정

이전에 풀었던 부분집합 문제와 거의 비슷하다.

1. 누적합이 C보다 크면 리턴한다.

2. 모든 레벨에 대해 탐색을 끝냈다면 result 변수와 누적합을 비교해서 최대값을 출력한다.

3. 탐색이 끝나지 않았다면 부분집합에 사용할때에는 DFS(L+1, sum+arr[L], arr) 을 매개변수로 넣어준다.

4. 부분집합에 사용하지 않을 때에는 DFS(L+1, sum, arr) 을 매개변수로 넣어준다.

---

풀이과정

1. 각 변수들을 선언 및 초기화한다.

• result : 결과를 저장할 변수로, Integer.MIN_VALUE 를 통해 최소값으로 초기화한다.
• sum : 개 무게의 누적합이다.

2. DFS 메소드를 작성한다.

 

3. sum이 C 보다 크다면 리턴한다.

• 누적합이 최대 무게인 C 보다 크다면 바로 리턴한다.

4. L과 N이 같다면 result와 sum 중에 최대값을 찾아 result에 저장한다.

• L과 N이 같다면 모든 레벨의 탐색을 끝냈다는 것을 의미한다.

5. L과 N이 다르다면 탐색을 계속해야 한다. 해당 원소가 부분집합에 사용된다면 DFS(L+1, sum+arr[L], arr) 을 매개변수로 넣어준다.

• sum에 배열의 원소 값을 누적시킨다.

7. 해당 원소가 부분집합에 사용되지 않는다면 DFS(L+1, sum, arr) 을 매개변수로 넣어준다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.