DFS 활용 - 부분 집합 관련 문제 모음

오늘은 탐색 알고리즘인 DFS를 활용하여 합이 같은 부분집합 구하기, 최대 무게 구하기, 최대 점수 구하기 총 3문제를 풀어보려고 합니다. Stack 활용을 모르신다면 이해하시기 어렵기 때문에, 관련 포스팅을 참고해 주세요😊

 

DFS 부분집합

개요

하단에서 풀어 볼 3개의 문제는 모두 DFS의 부분 집합을 활용하는 문제입니다. 첫 번째, 합이 같은 부분집합 구하기 문제를 잘 이해하시면 나머지 2개의 문제도 비슷한 맥락이기 때문에 이해하기 쉽습니다😊 

 

합이 같은 부분집합 구하기📙

문제 내용

이 문제의 포인트는 마지막 노드까지 갔을 때(부분 집합)의 총합을 구하는 방법과 각각의 부분 집합이 입력된 자연수 집합의 절반과 같은지 체크하는 것입니다.

 

예시에서 1, 3, 5, 6, 7, 10 집합이 주어졌고, 이 집합의 총합은 32이며 절반 값은 16입니다. 즉, DFS 탐색을 이용하여 마지막 노드까지의 합이 16인 곳이 있으면 합이 같은 부분집합을 구할 수 있는 것입니다.

 

그럼 코드로 문제를 풀어볼까요?

 

public class Subset {
    static String result = "NO";
    static int n, total = 0;
    boolean flag = false;
    
    public static void main(String[] args) {
        Subset T = new Subset();
        Scanner sc = new Scanner(System.in);
        n= sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
            total += arr[i];
        }
        T.DFS(0,0,arr);
        System.out.println(result);
    }
}

main 부터 확인해보면 Scanner로 자연 수 집합의 길이 n을 입력받고 반복문을 이용하여 배열을 완성시킵니다. 또한, 자연수 집합의 총합을 구해야 하기 때문에 total 값에 누적시켜 주었습니다. 

 

이후에 DFS() 함수를 호출시키는대 인자 값으로 L(Level), sum(총 합), arr(배열)을 넘겨주었습니다. DFS는 대게 if~else문을 주로 사용하는데 여기서 마지막 노드인지 체크하기 위해서 L 값을 넘겨주는 것입니다. 맨 처음은 0 레벨이지만 한 단계씩 노드가 내려갈수록 레벨을 증가시켜주는 구조입니다.

 

sum은 말 그대로 마지막 노드까지 갔을 때의 총합을 구하기 위한 변수이며 초기 값은 0으로 지정해줍니다. 마지막으로 DFS() 함수를 돌 arr 배열을 넘겨줍니다.

   public void DFS(int L, int sum, int[] arr) {
        if(flag) return;          // line 2
        if(sum > total/2) return; // line 3
        if(L == n) {
            if(total / 2 == sum) {
                result = "YES";
                flag = true;
            }
        } else {
            DFS(L+1, sum+arr[L], arr);
            DFS(L+1, sum, arr);
        }
    }

DFS 함수가 돌아가면서 만약 예제의 절반 값인 16을 찾게 된다면 더 이상 함수를 실행 시킬 필요가 없기 때문에 boolean 변수 flag를 true로 만들고 다음 함수부터 return 시켜주었습니다.(line 2)

 

또한, 부분 집합의 합계가 16보다 넘어가면 더 이상 밑에 노드까지 볼 필요가 없기 때문에 이 부분도 return 시켜주었습니다.(line 3)

 

if(L==n)은 현재 자연수 집합의 길이 n은 6이고, L은 앞서 언급했듯이 마지막 노드까지의 길이를 일컫습니다. 즉, {1(사용), 3(사용), 5(미사용), 6(사용), 7(미사용), 10(미사용)}이라고 가정했을 때, 모든 원소를 다 탐색했기 때문에 L은 6이 될 것이며 이 말은 마지막 노드까지의 부분집합을 구했다는 뜻입니다. 

 

else문에서는 DFS는 왼쪽 오른쪽으로 노드가 갈라지는데 여기서는 다음 노드(ex : 1의 다음 노드 3)를 사용을 한다면 왼쪽(DFS(L+1), sum+arr[L], arr), 사용을 안 한다면 오른쪽(DFS(L+1, sum, arr))으로 구성시켜 주었습니다. 

 

당연히 왼쪽 방향은 다음 노드를 사용하기 때문에 왼쪽으로 넘어가는 함수는 arr[L] 값을 포함시켜주어야 합니다.

 

쉽게 말해, 트리로 된 노드 구조에서 아래쪽으로 왼쪽 방향부터 노드가 내려가면서 사용하냐 안 하냐로 구분지어서 부분 집합을 구하게 되는 것입니다. 그리고 그 부분 집합의 합을 sum으로 누적하고 그 sum 값이 total의 절반이라면 YES로 바꿔주면 됩니다.

 

최대 무게 구하기📘

문제 내용

 

사실 위 부분 집합 문제를 이해하셨다면, 이번 문제도 코드가 거의 비슷하게 구현이 되기 때문에 쉽게 푸실 수 있을 것 같습니다😄

 

public class MaxWeight {
    static int result = Integer.MIN_VALUE, c, n;

    public static void main(String[] args) {
        MaxWeight T = new MaxWeight();
        Scanner sc = new Scanner(System.in);
        c = sc.nextInt();
        n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }
        T.DFS(0,0,arr);
        System.out.println(result);
    }
}

main은 위 문제처럼 입력받습니다. c는 트럭에 올릴 수 있는 최대 무게값이고, n은 바둑이들의 마리 수입니다. n만큼 반복문을 돌면서 배열을 생성하고, 바둑이들의 무게를 하나씩 입력받아 배열에 넣어줍니다.

 

그리고 DFS() 함수를 실행시키는대, 이번에도 L(레벨)과 sum(합계)은 초기 값을 0으로 설정합니다.

 

public void DFS(int L, int sum, int[] arr) {
        if(sum > c) return;
        if(L == n) {
            result = Math.max(result, sum);
        } else {
            DFS(L+1, sum+arr[L], arr);
            DFS(L+1, sum, arr);
        }
}

당연하지만 합계 sum이 최대 무게 c를 넘어가면 return 시켜주어야 합니다. 더 이상 아래 노드까지 확인하면서 내려갈 필요가 없기 때문입니다. 

 

if~else문도 비슷하게 구현됩니다. else문은 왼쪽(다음 노드 사용), 오른쪽(다음 노드 미사용)으로 나누어서 왼쪽부터 순차적으로 부분 집합의 합계를 구하게 됩니다.

 

if문은 동일합니다. 레벨이 총 바둑이의 수와 동일하게 된다면 해당 노드 집합은 모든 바둑이를 탐색한 것이므로 부분 집합이 되었고, 이 값을 result에 담게 됩니다.

 

하지만, 최대 무게를 구하는 것이기 때문에 각각의 부분집합을 Math.max() 함수를 이용해서 최댓값을 뽑아내면 됩니다😊

 

최대 점수 구하기📒

문제 내용

 

최대 점수 구하는 문제도 부분 집합을 활용합니다. 한 가지 다른점은 배열을 2개 사용해야 하는 점인대 바로 코드로 확인해 볼까요?

 

public class MaxScore {
    static int result = Integer.MIN_VALUE, n, m;

    public static void main(String[] args) {
        MaxScore T = new MaxScore();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for(int i = 0; i < n; ++i) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        T.DFS(0,0,0,a,b);
        System.out.println(result);
    }
}

첫 번째로 n은 총 문제 개수이고, m은 제한시간입니다. 그리고 a, b 두 개의 배열을 선언해 주었는데, a 배열에는 문제 점수가 들어가고, b 배열에는 문제를 푸는대 걸리는 시간이 들어갑니다.

 

그리고 지금까지와 마찬가지로 DFS() 함수를 실행시키고 인자값으로는 L(레벨), sum(합계), time(걸린 시간), a배열(문제 점수 배열), b배열(문제 당 걸리는 시간 배열)을 넣어줍니다.

 

public void DFS(int L, int sum, int time, int[] ps, int[] pt) {
        if(time > m) return;
        if(L == n) {
            result = Math.max(result, sum);
        } else {
            DFS(L+1, sum+ps[L], time+pt[L], ps, pt);
            DFS(L+1, sum, time, ps, pt);
        }
}

헷갈릴 수 있는 부분은 sum과 time입니다. sum은 a배열 즉, 문제 점수들의 합이고 time은 그 문제들을 푼 시간들의 합입니다. 문제에서는 제한 시간이 주어지기 때문에 첫 줄에 time(문제 푼 시간들의 합)이 m(제한 시간) 보다 크다면 return 시켰습니다. 굳이, 제한 시간이 넘어갔는데 아래 노드를 확인할 필요는 없기 때문입니다.

 

if~else 문은 최대 무게 구하기와 동일합니다. 마지막 노드에 다다르면 해당 값과 result 값을 비교해서 큰 값을 담아주면 되고, else 문에서는 왼쪽과 오른쪽으로 나누어서 진행시키는데 왼쪽 진행 시에만 합계에 누적해주면 됩니다😄 

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

마치며

지금까지 DFS를 활용한 부분 집합 문제를 풀어봤습니다. 혹시 이해가 안 되시는 부분은 댓글 달아주시면 좀 더 자세히 설명해 드릴게요! 다음 포스팅도 DFS를 활용한 문제 위주로 포스팅할 것 같네요. 다음 포스팅에서 뵐게요😄