인프런, 자바(Java) 알고리즘 문제풀이
DFS, BFS 활용 - 0802. 강아지 승차(DFS)
(해당 문제는 ㅂㅏ둑이 승차이지만, velog의 필터링 정책에 의해 강아지로 표기하였습니다.)
🗒️ 문제
🎈 나의 풀이
private static int m, w = 0;
private static int[] ch;
private static void DFS(int n, int[] arr) {
if(n >= arr.length) return;
int sum = 0;
for(int i=0; i<arr.length; i++) {
if(ch[i] == 0) {
if(sum + arr[i] > m) break;
sum+= arr[i];
}
}
w = Math.max(w, sum);
ch[n] = 1;
DFS(n+1, arr);
ch[n] = 0;
DFS(n+1, arr);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
int n = sc.nextInt();
int[] arr = new int[n];
ch = new int[n];
for(int i=0; i<n; i++) arr[i] = sc.nextInt();
DFS(0, arr);
System.out.println(w);
}🖍️ 강의 풀이
static int answer=Integer.MIN_VALUE, c, n;
public void DFS(int L, int sum, int[] arr){
if(sum>c) return;
if(L==n){
answer=Math.max(answer, sum);
}
else{
DFS(L+1, sum+arr[L], arr);
DFS(L+1, sum, arr);
}
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
c=kb.nextInt();
n=kb.nextInt();
int[] arr=new int[n];
for(int i=0; i<n; i++){
arr[i]=kb.nextInt();
}
T.DFS(0, 0, arr);
System.out.println(answer);
}💬 짚어가기
해당 문제는 DFS를 이용하여 풀 수 있다. 나의 풀이에서는 강아지의 갯수와 동일한
크기의 배열을 생성하여 해당 강아지를 차에 실을지의 여부를 체크하도록 하였다.
현재 바라보는 인덱스와 강아지 무게가 담긴 배열을 파라미터로 받도록 하고, 반복문을
수행하며 차량에 실을 수 있는 강아지(ch 배열에 체크되지 않은 강아지)들의 누적합을
확인한다.
차량에 실을 수 있는 무게를 초과하지 않을 때 까지 반복문을 수행하여 누적합을 계산하고
최대값을 갱신하도록 한다. 이후 현재 바라보는 인덱스의 강아지를 포함하는 경우와 그렇지
않은 경우를 나누어 재귀 호출하여 문제를 해결한다.
강의에서는 간결하고 더욱 직관적으로 풀이하였다. 파라미터로 현재 바라보는 인덱스와
누적합 그리고 강아지의 무게를 담고 있는 배열을 넘긴다.
만일 누적합이 차량의 최대 승차 무게를 초과하는 경우 바로 리턴하도록 하고, 그렇지 않은
경우 누적합에 해당 강아지의 무게를 포함하는 경우와 그렇지 않는 경우 두가지를 나누어
재귀 호출함으로 DFS를 수행한다.
바라보는 인덱스가 배열의 크기와 동일한 경우(모든 경우의 수를 확인 한 경우) 최대값을
갱신하여 문제를 해결한다.
𝑶𝒏𝒆 𝒅𝒂𝒚 𝒐𝒓 𝒅𝒂𝒚 𝒐𝒏𝒆.