[SWEA 2115] 벌꿀채취 (C++)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu

SW Expert Academy

1. 주의할 점

- 두 일꾼이 같은 선택된 벌꿀통을 고르면 안된다

- 각 칸을 기준으로 최대 M칸까지 오른쪽으로 골랐을때의 최대 가중치를 저장한다

 

2. 구현

- Check[][] 배열을 false로 초기화시켜서 같은 벌꿀통을 고르지 않도록 확인하기 위해 false로 전부 초기화한다

- DFS() 사용하여 해당 칸을 골랐을 때 기준으로 최대값을 (가중치의 내림차순 순서로 정의)우선순위큐에 저장한다

- M개의 벌꿀통중에서 특정 벌꿀통을 고르거나 고르지 않는 경우를 고려하기 위해 DFS를 사용한다(백트레킹)

- DFS에선 if (x == max_x || x == num) 조건문을 통해 최대 범위를 벗어나지 않도록 설정한다

- DFS에서 받는 매개변수는 (현재 Y, 현재 X, 초기 X + M, 벌꿀의 총합, 가중치(제곱들의 합))

- 우선순위큐에서 1개씩 추출하면서 같은 벌꿀통에서 골랐을 경우 Continue, 아닐 경우 뽑은 후, Check[][]배열을 설정하여 같은 벌꿀통에서 고르지 않도록 설정한다

- 위의 과정을 2명의 일꾼이 골랐을 때까지 반복한다

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
    int r, c, val;
};
struct cmp {
    bool operator()(info& a, info& b) {
        return a.val < b.val;
    }
};
info tmp;
int num, result, c, con, maxi;
int arr[10][10];
bool check[10][10];
priority_queue<info, vector<info>, cmp> pq;
 
void dfs(int y, int x, int max_x, int sum, int cal) {
    if (x == max_x || x == num) {       //최대 범위를 벗어난 경우
        maxi = max(maxi, cal);
        return;
    }
    if (arr[y][x] + sum <= c)            //채취한 경우
        dfs(y, x + 1, max_x, arr[y][x] + sum, cal + arr[y][x] * arr[y][x]);
    dfs(y, x + 1, max_x, sum, cal);     //채취 안한 경우
}
 
int main() {
    int test;
    cin >> test;
    for (int t = 1; t <= test; t++) {
        cin >> num >> con >> c;
        for (int i = 0; i < num; i++) 
            for (int j = 0; j < num; j++) {
                cin >> arr[i][j];
                check[i][j] = false;
            }
        //초기화
        while (!pq.empty())
            pq.pop();
        result = 0;
 
        for (int i = 0; i < num; i++)
            for (int j = 0; j <= num - con; j++) {
                maxi = 0;
                dfs(i, j, j + con, 0, 0);
                tmp.c = j;
                tmp.r = i;
                tmp.val = maxi;
                pq.push(tmp);
            }
        int remain = 0;
        while (!pq.empty()) {
            int cx = pq.top().c;
            int cy = pq.top().r;
            int cv = pq.top().val;
            pq.pop();
            bool avail = true;
            for (int i = cx; i < min(cx + con, num); i++) {
                if (check[cy][i]) {
                    avail = false;
                    break;
                }
            }
            if (avail) {
                result += cv;
                remain++;
                for (int i = cx; i < min(cx + con, num); i++) 
                    check[cy][i] = true;                                    
            }
            if (remain == 2) break;
        }
        cout << "#" << t << " " << result << '\n';
    }
    return 0;
}