Softeer-연습문제-함께하는 효도(C++)

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

난이도 : Lv.3

문제 개요 : 

친구들이 협동하여 최대로 수확할 수 있는 수확량 구하기

#include<iostream>
#include<vector>

using namespace std;

bool check(const vector<int> xy, const int N){
    const int x = xy[0];
    const int y = xy[1];
    if(0 <= x && x < N && 0 <= y && y < N){
        return true;
    }
    else{
        return false;
    }
}

int calculate(vector<vector<int>> map, vector<vector<int>> xy, int move_seed){
    // 상하좌우
    const vector<vector<int>> move = {{-1,0}, {1,0}, {0,-1}, {0,1}};

    int result = 0;
    
    for(int i=0; i<xy.size(); i++){
        result += map[xy[i][0]][xy[i][1]];
        map[xy[i][0]][xy[i][1]] = 0;
        for(int j=0; j<3; j++){
            xy[i][0] += move[move_seed % 4][0];
            xy[i][1] += move[move_seed % 4][1];
            move_seed /= 4;
            if(check(xy[i], map.size())){
                result += map[xy[i][0]][xy[i][1]];
                map[xy[i][0]][xy[i][1]] = 0;
            }
            else{
                return -1;
            }
        }
    }
    return result;
}

int main(int argc, char** argv)
{
    int n, m;
    scanf("%d %d", &n, &m);

    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>> xy(m, vector<int>(2));
    for(int i=0; i<m; i++){
        scanf("%d %d", &xy[i][0], &xy[i][1]);
        xy[i][0]--;
        xy[i][1]--;
    }

    int bruteforce = 1;
    for(int i=0; i<m; i++){
        bruteforce *= 64;
    }
    int max_val = 0;
    for(int i=0; i<bruteforce; i++){
        max_val = max(calculate(map, xy, i), max_val);
    }

    printf("%d", max_val);

   return 0;
}

 

문제 해결 방법

1. 친구 수가 해봤자 최대 3명이고, 상하좌우로 3번씩만 이동하므로 경우의 수가 얼마 되지 않는다. (경우의 수 : 4^3^3 개) 따라서 브루트포스를 사용하여 해결한다.

2. move_seed를 4^3^m(이때, m은 친구의 수)번 증가시키면서 모든 경우의 수를 계산한다.

3. 맵 밖으로 나갔는지 확인하는 check 함수를 만든다.

4. move_seed를 따라 움직였을 때 얻을 수 있는 수확량을 계산하는 calculate 함수를 만든다.

5. calculate 함수의 리턴값 중 최대인 값을 정답으로 출력한다.