Softeer-연습문제-나무 조경(C++)

문제 링크 : https://softeer.ai/practice/7594

난이도 : Lv.3

문제 개요 : 

나무를 2개씩 묶은 후 묶은 나무들의 키 합의 최댓값 구하기

경우의 수가 별로 없어서 브루트포스로 해결했다.

#include<iostream>
#include<vector>

using namespace std;

bool check(const vector<vector<int>> selected, const int row, const int col){
    for(int i=0; i<selected.size(); i++){
        if(selected[i][0] == row && selected[i][1] == col){
            return false;
        }
    }
    return true;
}

void calculate(vector<vector<int>> map, vector<vector<int>> &selected, int &max_value){
    const int n = map.size();
    if(selected.size() == 8){
        int result = 0;
        for(int i=0; i<selected.size(); i++){
            result += map[selected[i][0]][selected[i][1]];
        }
        selected.pop_back();
        selected.pop_back();
        if(max_value < result){
            max_value = result;
        }
        return;
    }
    for(int j=0; j < (n-1)*n*2; j++){ // (n-1)*n*2 가지 경우의 수
        if(j < (n-1)*n){
            int row = j / n;
            int col = j % n;
            if(check(selected, row, col) && check(selected, row+1, col)){
                selected.push_back({row, col});
                selected.push_back({row+1, col});
                calculate(map, selected, max_value);
           }
        }
        else{
            int row = (j - (n-1)*n) % n;
            int col = (j - (n-1)*n) / n;
            if(check(selected, row, col) && check(selected, row, col+1)){
                selected.push_back({row, col});
                selected.push_back({row, col+1});
                calculate(map, selected, max_value);
           }
        }
    }
    if(selected.size() > 0){
        int result = 0;
        for(int i=0; i<selected.size(); i++){
            result += map[selected[i][0]][selected[i][1]];
        }
        selected.pop_back();
        selected.pop_back();
        if(max_value < result){
            max_value = result;
        }
        return;
    }
}

int main(int argc, char** argv)
{
    int n;
    scanf("%d", &n);
    vector<vector<int>> map(n, vector<int>(n));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &map[i][j]);
        }
    }

    // 가로로 먼저 돌고
    vector<vector<int>> selected;
    int max_value = 0;
    calculate(map, selected, max_value);
    cout << max_value;

   return 0;
}

 

문제 해결 방법

1. 나무들의 키를 map에 저장한다.

2. 묶은 나무의 위치(x, y값)를 selected에 저장한다.

3. 재귀함수를 돌면서 n * n에서 나무 2개를 묶는 경우의 수(n*(n-1)*2가지)를 for문으로 모두 확인한다. 이때, check함수를 통해 이미 골랐던 나무를 또 선택했는지 체크한다. 재귀함수의 종료조건은 4묶음을 모두 묶었거나, 모든 경우의 수를 다 확인하고 for문을 빠져나온 경우이다. 함수를 종료하기 전에는 마지막에 선택했던 1묶음을 취소하고 종료한다.

4. 최댓값을 max_value에 저장하고, 마지막에 이를 출력한다.