SWEA 2115 [모의 SW 역량테스트] 벌꿀채취 C++

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE&&&

SW Expert Academy

 

최종 코드

• GitHub github.com/hwayeon351/SWEA-Algorithms

hwayeon351/SWEA-Algorithms

//
//  main.cpp
//  SWEA2115
//
//  Created by Hwayeon on 2021/10/17.
//

#include <iostream>
using namespace std;

int N, M, C;
int honey[11][11] = {0, };
int answer = 0;
int w1_earn = 0;
int w2_earn = 0;

void w1_earn_money(int x, int sx, int sy, int h, int money){
    if(x > sx+M) return;
    if(h > C) return;
    if(money > w1_earn) w1_earn = money;
    for(int xx=x; xx<sx+M; xx++){
        w1_earn_money(xx+1, sx, sy, h+honey[sy][xx], money + honey[sy][xx]*honey[sy][xx]);
    }
};

void w2_earn_money(int x, int sx, int sy, int h, int money){
    if(x > sx+M) return;
    if(h > C) return;
    if(money > w2_earn) w2_earn = money;
    for(int xx=x; xx<sx+M; xx++){
        w2_earn_money(xx+1, sx, sy, h+honey[sy][xx], money + honey[sy][xx]*honey[sy][xx]);
    }
};

void get_honey(int wx, int wy){
    w1_earn = 0;
    w1_earn_money(wx, wx, wy, 0, 0);
    int ny = wy;
    int nx = wx+M;
    if(nx > N-M){
        nx = 0;
        ny ++;
    }
    for(int y=ny; y<N; y++){
        if(y > ny) nx = 0;
        for(int x=nx; x<=N-M; x++){
            w2_earn = 0;
            w2_earn_money(x, x, y, 0, 0);
            int total = w1_earn+w2_earn;
            if(answer < total) answer = total;
        }
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        answer = 0;
        cin >> N >> M >> C;
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                cin >> honey[y][x];
            }
        }
        for(int y=0; y<N; y++){
            for(int x=0; x<=N-M; x++){
                if(y == N-1 && x > N-2*M) break;
                get_honey(x, y);
            }
        }
        cout << "#" << test_case << " " << answer << endl;
    }
    return 0;
}

 

---

풀이 과정

풀이 시간 1시간 19분

#include <iostream>
using namespace std;

int N, M, C;
int honey[11][11] = {0, };
int answer = 0;

//일꾼 w1, w2가 번 돈
int w1_earn = 0;
int w2_earn = 0;

void w1_earn_money(int x, int sx, int sy, int h, int money){
	//벌통 범위에서 벗어난 경우, 함수 종료
    if(x > sx+M) return;
    //C보다 많은 꿀을 채취한 경우, 함수 종료
    if(h > C) return;
    //채취한 꿀의 최대 수익으로 w1_earn 갱신
    if(money > w1_earn) w1_earn = money;
    
    //(sx, sy) ~ (sx+M, sy) 중 채취할 벌통 선택
    for(int xx=x; xx<sx+M; xx++){
        w1_earn_money(xx+1, sx, sy, h+honey[sy][xx], money + honey[sy][xx]*honey[sy][xx]);
    }
};

void w2_earn_money(int x, int sx, int sy, int h, int money){
	//벌통 범위에서 벗어난 경우, 함수 종료
    if(x > sx+M) return;
    //C보다 많은 꿀을 채취한 경우, 함수 종료
    if(h > C) return;
    //채취한 꿀의 최대 수익으로 w1_earn 갱신
    if(money > w2_earn) w2_earn = money;
    
    //(sx, sy) ~ (sx+M, sy) 중 채취할 벌통 선택
    for(int xx=x; xx<sx+M; xx++){
        w2_earn_money(xx+1, sx, sy, h+honey[sy][xx], money + honey[sy][xx]*honey[sy][xx]);
    }
};

void get_honey(int wx, int wy){
	//w1이 고른 M개의 벌통에서 벌꿀 채취 -> O(M)
    w1_earn = 0;
    w1_earn_money(wx, wx, wy, 0, 0);
    
    //w2 M개의 벌통 선택 -> O(N^2)
    int ny = wy;
    int nx = wx+M;
    if(nx > N-M){
        nx = 0;
        ny ++;
    }
    for(int y=ny; y<N; y++){
        if(y > ny) nx = 0;
        for(int x=nx; x<=N-M; x++){
        	//w2이 고른 M개의 벌통에서 벌꿀 채취 -> O(M)
            w2_earn = 0;
            w2_earn_money(x, x, y, 0, 0);
            
            //두 일꾼의 수익의 합의 최대값을 answer에 갱신
            int total = w1_earn+w2_earn;
            if(answer < total) answer = total;
        }
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        answer = 0;
        cin >> N >> M >> C;
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                cin >> honey[y][x];
            }
        }
        
        //w1 M개의 벌통 선택 -> O(N^2)
        for(int y=0; y<N; y++){
            for(int x=0; x<=N-M; x++){
                if(y == N-1 && x > N-2*M) break;
                get_honey(x, y);
            }
        }
        cout << "#" << test_case << " " << answer << endl;
    }
    return 0;
}
//시간복잡도 = O(M*N^4), 공간복잡도 = O(N^2)

 

---

이전 풀이

풀이 시간  1시간 49분

1. 벌통 선택 pick_honey()

void pick_honey(int cnt){
    vector<pair<int, int> > v;
    v.clear();
    if(cnt==2) {
        get_max_earn();
        return;
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<=N-M; j++){
            bool check = true;
            for(int m=j; m<j+M; m++){
                if(visit[i][m]==true){
                    check = false;
                    break;
                }
            }
            if(check == false) continue;
            else{
                for(int m=j; m<j+M; m++){
                    visit[i][m] = true;
                    v.push_back(make_pair(i, m));
                }
                worker.push_back(v);
                pick_honey(cnt+1);
                for(int m=j; m<j+M; m++){
                    visit[i][m] = false;
                }
                worker.pop_back();
                v.clear();
            }
        }
    }
}

 먼저, 두 일꾼이 서로 다른 벌통을 선택해야 하고, 각각의 일꾼은 가로로 연속되는 M개의 벌통을 선택해야한다.

나는 이를 DFS를 활용하여 구현했고, cnt == 2, 즉, 두 명의 일꾼이 벌통을 선택하면 수익을 구하고(get_max_earn()) 함수를 종료하도록 하였다.

한 명의 일꾼이 M개의 벌통을 선택하는 과정은 다음과 같다.

1. 연속된 M개의 벌통 중 이미 선택된 벌통이 있는지 체크한다.
2. 선택된 적 있는 벌통이 있다면, continue를 통해 다음 연속된 벌통들을 탐색한다.
3. 모두 선택된 적이 없는 벌통이라면, visit[i][m] = true를 해주고, 벌통의 위치를 담는 벡터 v에 push 해준다. M개의 벌통을 담은 v를 벡터 worker에 담아주고, pick_honey(cnt+1)를 호출하여 다른 일꾼이 벌통을 선택하도록 한다. 이 후, 선택한 M개의 벌통을 모두 visit[i][m] = false 하고, v.clear(), worker.pop_back()을 해줌으로써, 두 일꾼이 벌통을 선택하는 모든 경우의 수가 발생할 수 있도록 한다.

 

 

2. 수익 계산 get_max_earn()

void get_max_earn(){
    for(int i=0; i<2; i++){
        worker_earn[i] = 0;
        choice_honey(i, 0, 0);
    }
    if(worker_earn[0]+worker_earn[1] > max_earn) max_earn = worker_earn[0]+worker_earn[1];
}

 수익을 계산하려면 먼저, 각각의 일꾼이 채취할 수 있는 꿀의 최댓값인 C이하로 꿀을 채취해야 하므로, 벌통을 선택하는 과정이 필요하다.

 

 

채취할 벌통 선택 choice_honey()

void choice_honey(int w, int cnt, int earn){
    if(cnt >= M){
        int total = 0;
        for(int i=0; i<M; i++){
            if(wh[w][i] == true){
                total += pow(map[worker[w][i].first][worker[w][i].second], 2);
            }
        }
        if(total > worker_earn[w]) worker_earn[w] = total;
        return;
    }
    for(int i=0; i<M; i++){
        if(wh[w][i] == true) continue;
        if(map[worker[w][i].first][worker[w][i].second] + earn <= C){
            wh[w][i] = true;
            choice_honey(w, cnt+1, map[worker[w][i].first][worker[w][i].second] + earn);
            wh[w][i] = false;
        }
        else choice_honey(w, cnt+1, earn);
    }
}

 이 또한 벌통의 선택에 따라 발생하는 수익 중 최대를 뽑아내야 하기 때문에 DFS를 활용하였다.

선택한 벌통의 개수인 M번 탐색을 하면 채취 후 얻는 수익을 계산하고 탐색을 종료하도록 하였다.

1. wh[w][i] == true인 경우는 일꾼이 해당 벌통을 채취하려고 선택하였음을 의미하므로, continue하여 다음 벌통을 탐색한다.
2. wh[w][i] == false인 경우, 해당 벌통의 꿀의 양과 이전에 선택했던 꿀의 양인 earn의 합이 C보다 크지 않으면, 해당 벌통을 채취할 벌통으로 선택하고 재귀 함수를 호출한다. 이 후, 또 다른 경우의 수를 위해 wh[w][i] = false를 해준다.
3. 벌통의 꿀의 양과 earn의 합이 C보다 크면, 채취할 수 없으므로 choice_honey(w, cnt+1, earn)을 해준다.

 이렇게 일꾼이 채취할 벌통 선택이 끝나면, 각 벌통에 담긴 꿀의 양의 제곱만큼의 수익을 얻으므로 total에 더해준다.

total > worker_earn[w]이면 total이 해당 일꾼이 얻을 수 있는 최대 수익이다.

 

두 일꾼이 채취할 벌통 선택을 DFS로 하여 구해진 가장 큰 수익인 worker_earn을 더한 값이 max_earn보다 크면 max_earn = worker_earn[0]+worker_earn[1] 해준다.

 

 

---

참고

• 2021/01/11 - [C++] - [알고리즘] BFS와 DFS

[알고리즘] BFS와 DFS