SWEA - 벌꿀채취

벌꿀 채취 삼성모의 기출

벌꿀의 합을 DFS를 활용한 모든 경우의 수를 통해 더하는게 주요 포인트

import java.sql.Array;
import java.sql.CallableStatement;
import java.util.*;
import java.io.FileInputStream;



class Solution
{
    static int N, M, C;
    static int[][] map;
    static int resultMax = -987654321;
    static List<Pos> list;
    static boolean[] visited;

    static class Pos{
        int y;
        int x;
        int sum;

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

    public static void main(String args[]) throws Exception
    {

        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = sc.nextInt();
            M = sc.nextInt();
            C = sc.nextInt();
            resultMax = 0;
            map = new int[N][N];


            for(int y=0; y<N; y++){
                for(int x=0; x<N; x++){
                    map[y][x] = sc.nextInt();
                }
            }

            list = new LinkedList<>();

            for(int y=0; y<N; y++){
                for(int x=0; x<N; x++){

                    if(isValid(x)){
                        getMax(y,x);
                    }

                }
            }

            int ans = solve();

            System.out.println("#" + test_case + " " + ans);
        }
    }

    static int solve() {
        int max = 0;

        for(int i=0; i<list.size(); i++){

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

            for(int j= i+1; j<list.size(); j++){

                int y2 = list.get(j).y;
                int x2 = list.get(j).x;
                int sum2 = list.get(j).sum;

                if(y == y2 && x + M  > x2)
                    continue;

                int tot = sum + sum2;

                max = Math.max(tot, max);

            }

        }

        return max;
    }

    static void getMax(int y, int x) {

        int sum = 0;
        int profit = 0;

        for(int i=0; i<M; i++){

            sum += map[y][x+i];
            profit += map[y][x+i]*map[y][x+i];

        }

        if(sum <= C){
            list.add(new Pos(y, x, profit));
        } else {
            visited = new boolean[M];

            for(int i=1; i<M; i++){
                dfs(0,y,x,i,0,0,0);
            }
            list.add(new Pos(y,x,resultMax));
            resultMax = 0;

        }

    }

    static void dfs(int start, int y, int x, int N, int K, int sum, int profit) {

        if(N == K){
            resultMax = Math.max(resultMax, profit);
            return;
        }

        for(int i=start; i<M; i++){

            if(visited[i] == false && sum + map[y][x+i] <= C){
                visited[i] = true;
                dfs(i+1, y,x,N,K+1,sum + map[y][x+i], profit + map[y][x+i]*map[y][x+i]);
                visited[i] = false;
            }

        }



    }

    static boolean isValid(int x) {

        if(x+M > N ) return false;
        return true;

    }


}