[소프티어] 함께하는 효도 (C++)

👓 문제 설명

---

https://softeer.ai/practice/7727

---

💣 제한 사항

---

🚨 접근 방법

단순 BFS, 다익스트라로 접근 시 0이 아닌 경로를 안가는 경우가 발생하기 때문에
이미 지나온 길도 탐색하는 방문처리를 하지 않는 DFS로 풀이했다.
(3명의 사람이 4방향으로 최대 3칸 이동하는 모든 경우의 수)
-> 3! x (4 x 4 x 4) x (4 x 4 x 4) = 1,572,864로 시간초과는 발생하지 않는다.

순열로 최대 m(m<=3)의 사람의 순열을 구한 후 DFS를 실행한다.
파라미터로 지나온 경로를 누적시키고, depth == 3을 충족 시킬 때,
지나온 경로 값이 최대일 때 경로 값과 경로를 초기화시켜준다.
이후 DFS 종료가 되었을 때 해당 경로에 대한 값을 0으로 초기화한다.

---

🚈 풀이

#include<iostream>
#include<vector>
using namespace std;
int n,m;
int ans;
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
int arr[21][21];
int temp_arr[21][21];
int temp_sum;
bool isSelected[3];
int nums[3];
vector<pair<int,int>>save_paths;
vector<pair<int,int>>start_pos;
struct info{
    int y,x,cnt;
};

void init(){
    temp_sum=0;
    save_paths.clear();
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            temp_arr[i][j]=arr[i][j];
        }
    }
}

void input(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=0;i<m;i++){
        int y,x;
        cin>>y>>x;
        start_pos.push_back({y-1,x-1});
    }
}
bool isValid(int y,int x){
    return y>=0&&x>=0&&y<n&&x<n;
}
void dfs(int y,int x,int depth,vector<pair<int,int>>&paths){
    if(depth==3){
        int sum=0;
        bool visited[21][21]={false,};
        for(auto p:paths){
            int cy=p.first;
            int cx=p.second;
            if(!visited[cy][cx]){
                sum+=temp_arr[cy][cx];
                visited[cy][cx]=true;
            }
        }
        if(temp_sum<sum){
            temp_sum=sum;
            save_paths=paths;
        }
        return;
    }
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(!isValid(ny,nx))continue;
        paths.push_back({ny,nx});
        dfs(ny,nx,depth+1,paths);
        paths.pop_back();
    }
}

void permutation(int depth){
    if(depth==m){
        int temp_ans=0;
        init();
        for(int i=0;i<m;i++){
            temp_sum=0;
            
            int y=start_pos[nums[i]].first;
            int x=start_pos[nums[i]].second;
            
            vector<pair<int,int>>temp_paths;
            
            temp_paths.push_back({y,x});
            dfs(y,x,0,temp_paths);
            
            temp_ans+=temp_sum;
            for(auto p:save_paths){
                temp_arr[p.first][p.second]=0;
            }
        }
        ans=max(ans,temp_ans);
    }
    for(int i=0;i<m;i++){
        if(!isSelected[i]){
            isSelected[i]=true;
            nums[depth]=i;
            permutation(depth+1);
            isSelected[i]=false;
        }
    }
}

int main(int argc, char** argv)
{
    input();
    permutation(0);
    cout<<ans;
   return 0;
}