[C++/Softeer] Lv3. 함께하는 효도

https://softeer.ai/practice/7727

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

현대 소프티어 Lv3. 함께하는 효도 C++ 풀이

 

꽤나 까다로웠던 문제이다.

코테 공부를 다시 시작하면서 처음으로 푼 문제인데,

열심히 고민하면서 풀다보니 예전 실력이 금방 돌아온 느낌이다

---

1. 초안(테케만 맞음)

1. 캐릭터 근처의 4방향 탐색 후, max값으로 이동 → 3초 후 정지하도록 함
2. 근데 잘못된 방법이었음!!! 3번 이동하는 모든 경우를 탐색하고, 그 중 max값을 얻는 경우를 리턴해야함
3. grid 복사해서 여러명 지나가는 루트 체크, visited로 한명 지나가는 루트 체크

아래 코드는 비교적 쉬운 bfs로 경로를 탐색한 초안입니다....테케는 맞았지만 제출해보니 실패.

수정하다가 dfs로 풀어야한다는 것을 깨달았죠

 

int findMax(int X, int Y, int grid[20][20]){
    int x = X-1;
    int y = Y-1;
    queue<pair<int,int>> q;
    int fruit = grid[x][y];
    int nx=0; int ny=0; int maxtree = 0;
    int cnt = 0;
    grid[x][y] = 0; // 현재 위치도 열매 따야함
    q.push({x,y});

    while(cnt < 3){
        pair<int,int> p = q.front();
        q.pop();
        maxtree = 0;
        for(int i=0; i<4; ++i){
            int mx = p.first + move_x[i];
            int my = p.second + move_y[i];
            if(canMove(mx,my) && (maxtree < grid[mx][my])){
                maxtree = grid[mx][my];
                nx = mx; ny = my;
            }
        }
        q.push({nx,ny});
        fruit += maxtree;
        grid[nx][ny] = 0;
        cnt ++;
    }
    return fruit;
}

 

 

왜 dfs로 해야하나?

-> 깊이 우선으로 3초동안 끝까지 움직이는 모든 루트를 탐색해야함!

3초동안 첫번째 루트에서 딸 수 있는 열매의 sum을 구하고,

다시 출발점으로 돌아와서

두번째 루트에서 딸 수 있는 열매의 sum을 구하고,

... 반복

 

그리고 친구 1, 친구2가 있을때 순열로 순서를 바꿔서 반복하는것 까지는 캐치했는데

각 친구의 열매 max를 구하고

그 max 경로만 저장해서 열매 수를 0으로 만들어야 했음! (이미 열매를 딴 나무)

처음 봤을 땐 쉬워보이는 문제였는데, 구현이 생각보다 빡셌다

 

2. 풀이

dfs에서 current_fruit 전달하고, max fruit이 갱신될 때만 bestPath를 저장했는데 뭔가 이상해서 출력해보니

지역변수 비교가 잘못되고 있는지 그냥 돌리는 족족 순차적으로 값이 갱신되길래

fruit 최댓값이 나올 때마다 전역변수 벡터에 푸시해서, vector.back() 값을 비교하도록 수정했다.

→ max일때의 경로가 잘 저장됨. 전역 벡터가 답이었다…………

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int grid[20][20] = {0,};
int tmp[20][20] = {0,};
bool visited[20][20] = {false,};
bool route[20][20] = {false,};
int n; int m;
int move_x[4] = {0,1,0,-1};
int move_y[4] = {1,0,-1,0};
vector<pair<int, int>> bestPath;
vector<pair<int, int>> currentPath;
vector<int> results;

bool canMove(int nx, int ny){
    if(nx<0 || nx>=n || ny<0 || ny>=n) return false;
    return true;
}

int dfs(int x, int y, int time, int current_fruit) {
    if (time >= 3) {
        return current_fruit;
    }
    int max_fruit = current_fruit;
    for (int i = 0; i < 4; ++i) {
        int mx = x + move_x[i];
        int my = y + move_y[i];
        if (canMove(mx, my) && !visited[mx][my]) {
            int fruit = grid[mx][my];
            visited[mx][my] = true;
            currentPath.push_back({mx, my});
            int total_fruit = dfs(mx, my, time + 1, current_fruit + fruit);
            if (results.back() < total_fruit) {
                results.push_back(total_fruit); // 이거였음!!!!!!!!!
                max_fruit = total_fruit;
                if (time == 2) {
                    bestPath = currentPath;
                    // cout << max_fruit<<"/";
                    // for(auto i:bestPath) cout << i.first<<","<<i.second<<"\n";
                }
            }
            currentPath.pop_back();
            visited[mx][my] = false;
        }
    }
    return results.back();
}

int findMax(int x, int y){
    // cout << x<<","<<y<<")\n";
    int start_fruit = grid[x][y];
    visited[x][y] = 1;
    grid[x][y] = 0;
    results.push_back(start_fruit);
    int max_fruit = dfs(x, y, 0, start_fruit);
    visited[x][y] = 0;
    
    for(auto i:bestPath){
        // cout <<"("<< i.first<<"," << i.second<<") ";
        grid[i.first][i.second] = 0;
    }
    currentPath.clear();
    return max_fruit;
}

int main(int argc, char** argv)
{
    int friends[3][3] = {0,};
    int answer = 0;
    cin >> n >> m;
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j) {
            cin >> grid[i][j];
        }
    }
    for(int i=0; i<m; ++i) cin >> friends[i][0] >> friends[i][1];
    memcpy(tmp, grid, sizeof(grid));
    vector<int> mlist;
    for(int i=0; i<m; ++i) mlist.push_back(i);
    do {
        int max = 0;
        memcpy(grid, tmp, sizeof(tmp));
        for (int j = 0; j < m; ++j) {
            int fr = mlist[j];
            max += findMax(friends[fr][0]-1, friends[fr][1]-1);
            // cout << max << "///----\n\n";
        }
        if (answer < max) answer = max;
    } while (next_permutation(mlist.begin(), mlist.end())); // 잘못된 공백 문자 수정
    cout << answer;
   return 0;
}

 

 

휴 오랜만에 n시간 순삭~~