[소프티어] C++ 연습문제 함께하는 효도

함께하는 효도 문제를 C++로 풀어보았습니다.

 

 

C++ 연습문제 함께하는 효도

 

 

 문제

 

https://softeer.ai/practice/7727/history? questionType=ALGORITHM

 

문제는 맵을 탐색하는 기본 콘셉트의 문제였습니다. 문제는 최대 3명의 친구가 겹치지 않고 탐색해서 최댓값을 구하는 것이었습니다. bfs나 dfs로 풀면 될 것 같았는데 bfs로는 가능할지는 모르겠지만 더 복잡할 것 같아서 dfs를 활용해서 풀 계획을 세웠습니다.

주의해야 할 점은 2명 이상의 친구가 있을 때, 각 친구가 최댓값이 되는 경우, 겹칠 수 있습니다. 하지만 문제 제약 조건이 겹치지 않는 것이다보니 1번 친구가 최댓값을 찾은 뒤 겹치지 않게 2번 친구가 남은 경로 중에 최대값을 찾는 경우 1가지와 우선순위를 바꿔서 2번 친구가 최대값을 찾은 뒤 겹치지 않게 1번 친구가 남은 경로 중에 최대값을 찾는 경우 1가지가 있을 것이고 이 2가지의 경우 중 더 큰 값이 정답이 될 것입니다.

따라서 저는 3명의 친구의 순열을 구하고 순열이 구해졌을 때 그 우선순위 대로 최대값을 구하고, 다음 순위로 넘어갈 때에는 기존에 찾은 최대값 경로를 누적해서 다음 우선순위의 친구가 방문하지 않으면서 최대값을 구하도록 했습니다.

 

 

 코드

 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define MAX_N 20 +1
#define MAX_M 3

int n,m;
int map[MAX_N][MAX_N];
int check[MAX_N][MAX_N];
int temp_result;
int total_result;

int xdir[4] = {-1,1,0,0};
int ydir[4] = {0,0,-1,1};

struct f_pos{
    int x, y;
}f_pos[MAX_M];
vector<struct f_pos> path[3];
vector<struct f_pos> temp_path;

void dfs(int time, int x, int y, int m){

    if (time >= 3) {
        int sum = 0;
        for(auto i:temp_path){
            sum += map[i.x][i.y];
        }
        if (sum > temp_result) {
            temp_result = sum;
            path[m] = temp_path;
        }
        return;
    }

    for(int i=0;i<4;i++){
        int xx = x + xdir[i];
        int yy = y + ydir[i];
        
        if (xx <0 || xx >= n || yy < 0 || yy >= n) continue;
        if (check[xx][yy] != 1) {
            check[xx][yy] = 1;
            temp_path.push_back({xx,yy});
            dfs(time+1,xx,yy, m);
            check[xx][yy] = 0;
            temp_path.pop_back();
        }
        
    }
    
}

int permu[3];
int permu_check[3];
void permutation(int n, int m){
    if (n>=m) {
        int total_sum = 0;
        for(int i=0;i<m;i++){
            check[f_pos[permu[i]].x][ f_pos[permu[i]].y] = 1;
            temp_path.push_back({f_pos[permu[i]].x, f_pos[permu[i]].y});
            dfs(0,f_pos[permu[i]].x, f_pos[permu[i]].y, i); 
            for(int i=0;i<MAX_N;i++)
                for(int j=0;j<MAX_N;j++)
                    check[i][j] = 0;
            for(int k=0;k<=i;k++) {
                for(auto i:path[k]) {
                    check[i.x][i.y] = 1;
                }
            }
            temp_path.clear();
            total_sum += temp_result;
            temp_result = 0;
        }
        if(total_sum > total_result)
            total_result = total_sum;
    }
    
    for(int i=0;i<m;i++){
        if(permu_check[i]!=1){
            permu_check[i] = 1;
            permu[n] = i;
            permutation(n+1,m);
            permu_check[i] = 0;
        }
    }

}


int main(int argc, char** argv)
{
    //input
    cin >> n;
    cin >> m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin >> map[i][j];

    for(int i=0;i<m;i++){
        int x, y;
        cin >> x;
        cin >> y;
        f_pos[i].x = x - 1;
        f_pos[i].y = y - 1;
    }

    permutation(0, m);

    cout << total_result;
    
   return 0;
}

 

생각보다 구현에 실수를 좀 했는데 돌이켜보자면,

 

변수를 잘 관리할 수 있도록 좀 더 깨끗하게 작성할 수 있을 것 같습니다. dfs와 같은 형태가 2개가 중복되다 보니 변수 관리가 헷갈렸습니다. 좀 더 깔끔하게 정리해서 변수를 작성한다면 초기화 이슈로 인한 디버깅 시간이 줄어들 것입니다.

항상 index를 어떻게 처리할지 확실하게 잡고 가야 합니다. (맵에서 0부터 시작할지 1부터 시작할지)

저는 0부터 시작하는 걸 선호하는데, 문제에서 입력이 1부터 시작하는 것으로 주어서, 변환하는 작업을 해줘야 했습니다.

vector를 사용하지 않았을 때에도 쉽게 구현할 수 있어야 할 것 같습니다. vector를 쓰면 편하지만 사용방법을 잊어버릴 수도 있기 때문에 path 정보를 저장하기 위한 변수를 빠르게 구현해야 할 것 같습니다.

 

 

 결론

 

단순해 보였지만 dfs 구현 연습을 하기에 좋은 문제였던 것 같습니다.