[SWEA] 2115번 벌꿀채취

2115번 벌꿀채취

문제 링크

 

해결방법

DFS + 백트래킹으로 모든 경우를 탐색해보는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

1. 먼저 한 일꾼의 벌꿀 채취 범위를 정한다
2. 가로 상의 m개의 벌통을 선택했다면 다음 일꾼이 벌통을 선택하는 탐색으로 넘어간다
3. 두 일꾼 모두 벌통을 선택했다면, 각 범위에서 최대 벌꿀 채취양을 구한다

 

두명의 일꾼이 벌통을 선택하는 경우 + 선택된 벌통에서 최대 벌꿀의 양을 구하는 과정 모두 DFS 백트래킹을 사용해야한다

 

문제 조건

• DFS + 백트래킹
• N ≤ 10
• M : 선택할 수 있는 벌통
• C : 한명의 일꾼이 채취할 수 있는 최대 벌꿀의 양

 

 

소스코드

문제 해결 시간 : 1h

메모리 : 12640 KB

시간 : 107 ms

#include <iostream>
#include <math.h>
#include <cstring>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;

int testcase;
int n,m,c,ans;
int res1,res2;
int map[11][11];
bool visited[11][11];

vector<vector<int>> honey;

// 벌꿀을 채취하는 경우와 그렇지 않는 경우 중 최대값을 찾음
int getMax(int num,int ind,int sum,int res){
    if(sum > c) return 0;
    if(ind == m) return res;
    
    int add = honey[num][ind]*honey[num][ind];
    return max(getMax(num,ind+1,sum+honey[num][ind],res+add), getMax(num,ind+1,sum,res));
}

void dfs(int r,int cnt){
    // 두 명의 일꾼이 모두 벌통을 선택했다면
    if(cnt == 2){
        res1 = getMax(0,0,0,0);
        res2 = getMax(1,0,0,0);
        
        ans = max(ans,res1+res2);
        return;
    }
    
    // DFS 탐색
    for(int i=r; i<n; i++){
        for(int j=0; j<n; j++){
            
            // 가로상의 m개의 벌통이 존재한다면
            bool flag1 = true;
            if(j+m > n){
                flag1 = false;
            }
            if(!flag1) continue;
            
            // 가로상의 m개의 벌통 사용 가능
            bool flag2 = true;
            for(int k=j; k<j+m; k++){
                if(visited[i][k]){
                    flag2 = false;
                    break;
                }
            }
            if(!flag2) continue;
            
            // 백트래킹
            vector<int> tmp;
            
            for(int k=j; k<j+m; k++){
                visited[i][k] = true;
                tmp.push_back(map[i][k]);
            }
            honey.push_back(tmp);
            
            dfs(i,cnt+1);
            
            honey.pop_back();
            for(int k=j; k<j+m; k++){
                visited[i][k] = false;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=1; t<=testcase; t++){
        // 초기화
        honey.clear();
        
        // 입력
        cin >> n >> m >> c;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> map[i][j];
            }
        }
        
        memset(visited, false, sizeof(visited));
        ans = 0;
        dfs(0,0);
        
        cout << "#" << t << " " << ans << "\n";
    }
    
    return 0;
}