[SWEA] 모의 SW 역량 테스트 2115번 벌꿀 채취 (java) 풀이 (완전 탐색, dfs)

sw expert academy 2115번 벌꿀 채취 자바(java) 풀이

• 모의 SW 역량테스트 벌꿀 채취
• sw expert academy 2115번 벌꿀 채취
  
  
  

문제정리

1. NxN의 벌통이 주어진다.
2. 꿀을 채취할 수 있는 벌통의 수 M이 주어진다.
3. 두 명의 일꾼은 가로로 연속되도록 M개의 벌통을 선택하여 채취할 수 있다.
4. 하나의 벌통에서 채취한 꿀은 하나의 용기에 담아야 한다.
5. 하나의 벌통에서 꿀을 채취할 때, 벌통에 있는 모든 꿀을 한번에 채취해야 한다. (일부분만 채취할 수 없다.)
6. 두 일꾼이 각각 채취할 수 있는 꿀의 최대 양은 C이다. (넘으면 넘지 않는 선에서만 채취 가능)
7. 수익은 각 용기에 있는 꿀의 양의 제곱만큼의 수익이 생긴다.
   
   
   

문제풀이

계산해야 하는 값이 많지 않으므로 모든 경우를 탐색해주면 됩니다.

1. M개의 벌꿀통을 채취할때 모든 가능한 경우에 따른 최대값을 모두 구합니다. (가로로 연속해서만 M개를 고를 수 있으므로 열의 index + M이 벌집통의 크기를 넘으면 가지치기를 합니다.)
   NxN의 벌집을 sliding방식으로 모든 경우를 탐색합니다.
   이때 M개 벌집의 꿀의 양이 C를 넘으면 그 범위 안에서 1개부터 M-1개 까지 고르는 모든 경우의 수를 따져서 가장 큰 경우를 찾아줍니다.
   찾은 (x,y)의 시작 범위와 최대 값을 list에 저장합니다.
2. list에 담긴 가능한 모든 경우를 가지고 수익의 합의 최대값을 update 합니다.
   이때 행이 같고 열이 겹쳐서 같은 꿀통을 따려고 하는 경우는 가지칩니다.
   
   
   

로직 설명

1번 테스트 케이스를 예로 들겠습니다.

4 2 13
6 1 9 7
9 8 5 8
3 4 5 3
8 2 6 7

이 경우 2개씩 채취 가능한 경우는 한 행에 3가지씩 총 12가지가 가능합니다.

1. (0,1)
   이 위치로부터 2개의 값은 6과 1 입니다. 합이 C를 넘지 않으므로 최대수익은 37
2. (0,2)
   이 경우도 C를 넘지 않으므로 최대 수익은 82
3. (0,3)
   이 경우는 합이 16으로 C를 넘습니다. 그러므로 가능한 경우는 9만을 채취하는것이 가장 큰 수익을 얻을 수 있으므로 81
   ...
4. (1,1)
   이 경우 합이 딱 13으로 C를 넘지 않습니다. 그러므로 최대 수익은 64+25
   ...
5. (3,2)
   이 경우도 합이 딱 13으로 C를 넘지 않습니다. 그러므로 최대 수익은 36+49

이 모든 list를 같은 벌꿀 통을 채취하는 것이 아닌지 확인하며 최대값을 갱신해 나갑니다.
그때 5번째 (1,1)에서 시작해서 2통을 따고, 12번째 (3,2)에서 시작해서 2통을 따는 경우의 수익을 합한 경우가 174로 가장 크므로 최대 수익은 174가 됩니다.

swea 2115번 벌꿀 채취 자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.LinkedList;

class Pos{
    // x: 시작위치(행 index)
    // y: 시작위치(열 index)
    // sum: 최대수익
    int x;
    int y;
    int sum;

    Pos(int x, int y, int sum){
        this.x = x;
        this.y = y;
        this.sum = sum;
    }
}

class Solution {
    static int N, M, C;
    static int[][] honey;
    static List<Pos> list;
    static boolean[] visited;
    static int max;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testNum = Integer.parseInt(br.readLine());
        for(int test=1; test<=testNum; test++) {
            String[] temp = br.readLine().split(" ");
            N = Integer.parseInt(temp[0]);
            M = Integer.parseInt(temp[1]);
            C = Integer.parseInt(temp[2]);

            honey = new int[N][N];
            for(int i=0; i<N; i++){
                temp = br.readLine().split(" ");
                for(int j=0; j<N; j++){
                    honey[i][j] = Integer.parseInt(temp[j]);
                }
            }

            max = 0;
            list = new LinkedList<>();

            // 모든 가능한 경우 탐색
            // 가능한 최대 합을 모두 구해놓기
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    // M개의 벌꿀통을 고를 수 있는지 확인 (가로로 연속해서만 고를 수 있기 때문)
                    if(isValid(j))
                        getMax(i, j);                    
                }
            }
            // 가능한 조합을 가지고 최대값 구하기
            System.out.println("#" + test + " " + solve());
        }
        br.close();
    }

    public static void getMax(int x, int y){
        int sum = 0;
        int profit = 0;
        // 시작 위치 (x,y)로 부터 M개의 벌꿀 채취할 경우 벌꿀 양의 합과 수익 구하기
        for(int i=0; i<M; i++) {
            sum += honey[x][y+i];
            profit += honey[x][y+i]*honey[x][y+i];
        }

        // M개 모두 골랐을때 벌꿀의 합이 sum보다 작으면 그것이 최대 수익
        if(sum <= C)
            list.add(new Pos(x, y, profit));
        else {
            visited = new boolean[M];
            // 1~M-1개를 고르는 경우 모두 check
            // 최대 수익을 구한다.
            for(int i=1; i<M; i++)
                dfs(x,y,0,i,0,0,0);
            list.add(new Pos(x, y, max));
            max = 0;
        }
    }

    public static boolean isValid(int j){
        if(j + M  > N) return false;
        return true;
    }

    public static void dfs(int x, int y, int k, int N, int sum, int profit, int start){
        if(k == N){
            max = max < profit ? profit : max;
            return;
        }

        for(int i=start; i<M; i++){
            if(!visited[i] && sum + honey[x][y+i] <= C){
                visited[i] = true;
                dfs(x, y, k+1, N, sum + honey[x][y+i], profit + honey[x][y+i]*honey[x][y+i], i+1);
                visited[i] = false;
            }
        }
    }

    public static int solve() {
        int max = list.get(0).sum;

        // 가능한 경우 중 2개를 골라 겹치지 않으면
        // 수익의 합을 구해 max profit을 update 해준다.
        for(int i=0; i<list.size(); i++) {

            int sum = list.get(i).sum;
            int x = list.get(i).x;
            int y = list.get(i).y;

            for(int j=i+1; j<list.size(); j++) {
                int x2 = list.get(j).x;
                int y2 = list.get(j).y;
                // 같은 꿀통을 딸 수 없음. 겹치면 안됨
                if(x == x2 && y+M > y2)
                    continue;

                int sum2 = list.get(j).sum;
                int tot = sum + sum2;
                max = max < tot ? tot : max;
            }
        }
        return max;
    }
}