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

📌 문제 설명

철수는 시장에 가기 위해 트럭에 바둑이들을 태우려고 한다.
하지만 트럭은 최대 C kg까지만 적재 가능하며
총 N마리 바둑이들의 무게가 주어질 때
C를 넘지 않으면서 태울 수 있는 최대 무게를 구하는 프로그램을 작성하라.

---

📝 입력 & 출력

입력

• 첫 줄: 트럭의 허용 무게 C (1 ≤ C ≤ 100,000,000), 바둑이 수 N (1 ≤ N ≤ 30)
• 둘째 줄부터: N마리 바둑이의 무게가 한 줄에 하나씩 주어진다.

출력

• 첫 줄: 트럭에 태울 수 있는 가장 무거운 무게

---

🔹 예제 입력 & 출력

예제 입력

 

259 5
81
58
42
33
61

예제 출력

 

242

---

💡 해결 방법

✅ 접근 방법

• 가능한 모든 바둑이 조합을 부분집합 형태로 탐색한다.
• DFS를 이용해 각 바둑이를 태우거나 태우지 않는 두 가지 경우로 분기
• 누적된 무게 sum이 C를 초과하지 않으면서 최대가 되는 값을 추적

✅ 가지치기 가능

• 바둑이 수 N이 최대 30이므로 모든 조합은 2^30 ≈ 10^9
• 단순 DFS만으론 시간 초과 가능성 있음
• 가지치기 조건을 넣어 탐색을 줄이면 효과적임 (sum > C일 경우 조기 종료 등)

---

💻 코드 구현 (Java)

package partDfsBfs;

import java.util.*;

public class Problem2 {
	static int C, N;
	static int[] arr;
	static int answer = 0;

	public void DFS(int L, int sum) {
		if (sum > C) return; // ❗ 가지치기: 이미 용량 초과 시 중단
		if (L == N) {
			answer = Math.max(answer, sum);
		} else {
			DFS(L + 1, sum + arr[L]); // 현재 바둑이를 태움
			DFS(L + 1, sum);          // 현재 바둑이를 태우지 않음
		}
	}

	public static void main(String[] args) {
		Problem2 T = new Problem2();
		Scanner kb = new Scanner(System.in);
		C = kb.nextInt();
		N = kb.nextInt();
		arr = new int[N];
		for (int i = 0; i < N; i++) arr[i] = kb.nextInt();
		T.DFS(0, 0);
		System.out.println(answer);
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 입력 및 초기화

C = kb.nextInt();
N = kb.nextInt();
arr = new int[N];

• 트럭 최대 적재 무게와 바둑이 수 입력

---

2️⃣ DFS 함수

public void DFS(int L, int sum)

• L: 현재 인덱스
• sum: 현재까지 태운 바둑이 무게의 합

---

3️⃣ 가지치기 (최적화)

if (sum > C) return;

• 이미 허용 무게를 초과했다면 더 이상 탐색할 필요 없음

---

4️⃣ 종료 조건

if (L == N) answer = Math.max(answer, sum);

• 바둑이 N마리 모두 확인했을 경우 최대 무게 갱신

---

5️⃣ 포함 / 미포함 분기

DFS(L + 1, sum + arr[L]);
DFS(L + 1, sum);

• 현재 바둑이를 태우는 경우와 태우지 않는 경우로 분기

---

⏳ 시간 복잡도 분석

• 전체 경우의 수: 2^N → N=30이면 약 10억 개
• 가지치기 없을 때: 최악의 경우 O(2^30)
• 가지치기 적용 시,평균 탐색 횟수는 훨씬 감소

---

🧠 핵심 정리

• 조합 문제에서 최대/최소 값을 구할 땐 DFS가 효과적
• sum > C일 때 가지치기(Pruning) 를 적용해 탐색 시간을 줄일 수 있음
• 완전탐색으로 충분히 풀 수 있는 범위 내에서는
  부분집합 구성 + 조건 필터링 방식이 직관적이고 구현이 간결함

---

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

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

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