[SWEA] 4012번 요리사

4012번 요리사

문제 링크

 

해결방법

DFS + 백트래킹을 통해 모든 경우를 탐색하는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

백준의 스타트와 링크 문제와 거의 동일하다

1차 구현에서는 2개의 음식에 재료를 배분하고, 배분이 균등하지 않다면 return 하는 식으로 구현했다

하지만, 이는 시간적인 측면에서 비효율적이었다

따라서 2차 구현 시, 균등하게 배분하도록 구현하였다!

 

 

소스코드

[1차 소스코드]

문제 해결 시간 : 30m

메모리 : 12632 KB

시간 : 2403 ms

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 16
#define INF 987654321
using namespace std;

int testcase;
int n,ans;
int map[MAX][MAX];
int selected[MAX];

int getDifference(vector<int> &f1, vector<int> &f2){
    int synergy1 = 0;
    int synergy2 = 0;
    
    // 음식에 대한 시너지
    for(int i=0; i<n/2; i++){
        for(int j=0; j<n/2; j++){
            if(i==j) continue;
            
            synergy1 += map[f1[i]][f1[j]];
            synergy2 += map[f2[i]][f2[j]];
        }
    }
    
    return abs(synergy1 - synergy2);
}

// 음식 1,2 에 식재료를 나누는 DFS 탐색
void dfs(int ind){
    // 모든 식재료를 선택했다면
    if(ind == n){
        vector<int> f1,f2;
        for(int i=0; i<n; i++){
            if(selected[i] == 1) f1.push_back(i);
            else if(selected[i] == 2) f2.push_back(i);
        }
        
        // n/2 씩 분배되지 않았다면
        if(f1.size() != f2.size()) return;
        
        ans = min(ans,getDifference(f1,f2));
        return;
    }
    
    // 음식 1 에 식재료 배분
    selected[ind] = 1;
    dfs(ind+1);
    
    // 음식 2 에 식재료 배분
    selected[ind] = 2;
    dfs(ind+1);
}

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++){
        cin >> n;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> map[i][j];
            }
        }
        
        ans = INF;
        dfs(0);
        
        cout << "#" << t << " " << ans << "\n";
    }
    
    return 0;
}

[2차 소스코드]

문제 해결 시간 : 30m

메모리 : 12632 KB

시간 : 2403 ms

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

int testcase;
int n,ans;
int map[MAX][MAX];
int selected[MAX];

int getDifference(vector<int> &f1, vector<int> &f2){
    int synergy1 = 0;
    int synergy2 = 0;
    
    // 음식에 대한 시너지
    for(int i=0; i<n/2; i++){
        for(int j=0; j<n/2; j++){
            if(i==j) continue;
            
            synergy1 += map[f1[i]][f1[j]];
            synergy2 += map[f2[i]][f2[j]];
        }
    }
    
    return abs(synergy1 - synergy2);
}

// 음식1,2 에 식재료를 나누는 DFS 탐색
void dfs(int ind,int cnt){
    if(cnt == n/2){
        vector<int> f1,f2;
        for(int i=0; i<n; i++){
            if(selected[i] == 1) f1.push_back(i);
            else f2.push_back(i);
        }
        
        ans = min(ans,getDifference(f1,f2));
        return;
    }
    
    for(int i=ind; i<n ;i++){
        if(selected[i] == 0){
            selected[i] = 1;
            dfs(i+1,cnt+1);
            selected[i] = 0;
        }
    }
}

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++){
        cin >> n;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> map[i][j];
            }
        }
        
        ans = INF;
        dfs(0,0);
        
        cout << "#" << t << " " << ans << "\n";
    }
    
    return 0;
}