[swexpert] 2115. 벌꿀 채취 (java, 백트래킹, 완전탐색)

a라는 사람과 b사람이 벌꿀을 채취하는데 벌집이 중복되지 않도록 해야된다.

a라는 사람은 모든 행, 열 기준으로 고르는데 b라는 사람은 a와 같은 행이라면 열이 중복되지 않도록 해야하고 다른 행이면 상관없이 뽑는다.

 

1. collect 함수 

a는 모든 경우를 전사적으로 구해주므로 list에 집어넣는다. (추후 다른 행이면서 열이 중복된 경우를 계산할 때 쓴다)

b는 a와 행이 겹치지 않는 부분에서 subset을 돌려준다.

일단 이 함수에서 a의 최대값과 b의 최대값의 합의 최대값으로 answer를 갱신해주면 행은 같은 경우는 끝난다.

 

2. calculate함수

다른 행의 중복된 열을 구해준다. a라는 사람은 collect함수에서 전사적으로 모든 subset 경우를 구해줬다.

a사람이 구한 리스트지만 이제 b도 같이 사용한다. 

이중 포문을 돌면서 row(행번호)가 같지 않을 때의 합을 구하고 최대값으로 answer를 갱신해준다.

 

 

package algo0422;

import java.util.ArrayList;
import java.util.Scanner;

class Info{
	int row;
	int sum;
	public Info(int row, int sum) {
		super();
		this.row = row;
		this.sum = sum;
	}
}

public class S_2115_벌꿀채취_Solution {
	static int t,n,m,c;
	static int[][] map;
	static int answer;
	static ArrayList<Info> alist;
	static int asum,bsum;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		t=sc.nextInt();
		for (int tc =1; tc <=t; tc++) {
			n=sc.nextInt();
			m=sc.nextInt();
			c=sc.nextInt();
			map=new int[n][n];
			alist=new ArrayList<>();
			answer=0;
			asum=0;
			bsum=0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j]=sc.nextInt();
				}
			}
			//벌꿀 채취
			collect();
			calculate();
			System.out.printf("#%d %d\n",tc,answer);
		}
	}

	private static void calculate() {
		//다른 행에서 열 중복하게 고른 것은 여기서 처리
		for (int i = 0; i < alist.size(); i++) {
			for (int j = 0; j < alist.size(); j++) {
				if(alist.get(i).row==alist.get(j).row)continue;//같은 열이면 넘어간다.
				int result=alist.get(i).sum+alist.get(j).sum;
				if(answer<result)answer=result;
			}
		}
		
	}

	private static void collect() {
		//같은 행에서 a와 b가 같이 고른 경우는 여기서 처리 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j<=n-m; j++) {//시작 열
				asum=0;
				subset(i,j,0,0,0,'a');//a고름
				bsum=0;
				for (int j2 = j+m; j2 <=n-m; j2++) {
					subset(i,j2,0,0,0,'b');//중복안되게 b고름
				}
				if(answer<asum+bsum)answer=asum+bsum;
			}
		}
		
	}
	
	private static void subset(int row,int col,int cnt,int sum,int powerSum,char person) {
		if(sum>c)return;//기준 용량 넘으면 return
		if(cnt==m) {//최대 m개
//			행 번호와 구한 값 넣기
			
			if(person=='a') {//a는 모든 경우를 구하므로 리스트에 넣어준다. 추후 행만 다른 경우를 고르기 위해서
				if(powerSum>asum)asum=powerSum;
				alist.add(new Info(row,powerSum));
			}else {
				if(powerSum>bsum)bsum=powerSum;
			}
			return;
		}
		subset(row,col+1,cnt+1,sum+map[row][col],powerSum+map[row][col]*map[row][col],person);
		subset(row,col+1,cnt+1,sum,powerSum,person);	
	}
}