소프티어

+추가 조건 고려해서 푸니까 더 안되네요. 보통 이 정도는 다 푼다는 이유로 아무도 답장 안해주시네요..야속해라

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


constexpr int CNT = 3; // 3초 동안 이동
typedef pair<int, int> iter2dim;
vector<vector<int>> farm;
vector<vector<int>> visited;
iter2dim i2dim[4] = {
    make_pair(-1, 0),
    make_pair(1, 0),
    make_pair(0, -1),
    make_pair(0, 1)
};
int N, M;


bool avail(int x, int y) {
    if (x < 0 or y < 0) return false;
    if (x >= N or y >= N) return false;
    return true;
}


int dfs(int x, int y, int depth) {
    if (!avail(x, y) || visited[x][y] == depth) return 0;
    if (depth > CNT) return 0;
    int currFruit = farm[x][y];
    visited[x][y] = depth; // 방문 처리
    int maxFruits = currFruit;
    for (int i = 0; i < 4; i++) {
        int tmpX = x + i2dim[i].first, tmpY = y + i2dim[i].second;
        if (avail(tmpX, tmpY) && depth != visited[tmpX][tmpY]) {
            maxFruits = max(maxFruits, currFruit + dfs(tmpX, tmpY, depth + 1));
        }
    }
    visited[x][y] = 0; // 백트래킹을 위해 방문 기록 초기화
    return maxFruits;
}


int main() {
    cin >> N >> M;
    farm.resize(N, vector<int>(N));
    visited.resize(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> farm[i][j];
        }
    }
    vector<iter2dim> friends(M);
    for (int i = 0; i < M; i++) {
        cin >> friends[i].first >> friends[i].second;
        friends[i].first--;
        friends[i].second--;
    }


    int totalMaxFruits = 0;
    for (const auto& f : friends) {
        fill(visited.begin(), visited.end(), vector<int>(N, -1)); // 방문 기록 초기화
        int tempMaxFruits = dfs(f.first, f.second, 0);
        totalMaxFruits += tempMaxFruits;
    }


    cout << totalMaxFruits << endl;
    return 0;
}

+ BFS도 시도했습니다. 대체 어쩌라는 건지도 모르겠네요;; 또 테케 1만 통과.

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> iter2dim; //2차원 iter라고 생각해서 네이밍했어요..
priority_queue<pair<int,iter2dim>> check_max;




iter2dim i2dim[4] = {
    make_pair(-1,0),
    make_pair( 1,0),
    make_pair(0,-1),
    make_pair(0, 1)
};
int N; //인자로 넘기자니 이런거까지 그래야 하나 싶어서 걍 전역변수 했습니다


int ** farm;
int ** visited;
int ** farm_origin, ** visited_origin;


bool is_unavail(int x, int y) {
    if(x<0 or y<0) return true;
    if(x>=N or y>=N) return true;
    return visited[x][y]>0;
}


int bfs(int x, int y) {
    if(is_unavail(x,y)) {
        return 0;
    }
    queue<iter2dim> q;
    cout << "\n\n";
    cout << visited[x][y] << '\n';
    if(!visited[x][y]) visited[x][y] = 1;
    q.push(make_pair(x,y));
    while(q.size()) {
        iter2dim cur = q.front();
        x=cur.first, y = cur.second;
        if(visited[cur.first][cur.second]==4) {
            while(q.size()) q.pop();
            return farm[cur.first][cur.second];
        }
        q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = i2dim[i].first+cur.first, ny = i2dim[i].second+cur.second;
            if(is_unavail(nx,ny)) continue;
            check_max.push(make_pair(farm[nx][ny]+farm[x][y], make_pair(nx,ny)));
        }
        if(check_max.size() == 0) return farm[x][y];
        iter2dim nxt = check_max.top().second;
        if(visited[nxt.first][nxt.second]>0)  {
                while(check_max.size()) check_max.pop();
                return farm[x][y];
                }
        cout << farm[x][y] << '+' << farm[nxt.first][nxt.second] << '=' << check_max.top().first << '\n';
        visited[nxt.first][nxt.second] = visited[x][y]+1;
        farm[nxt.first][nxt.second] = check_max.top().first;
        q.push(nxt);
        check_max.pop();
        while(check_max.size()) {
                check_max.pop();
                }
    }
    return 0;
}
//BFS+우선순위큐로 탐색 바꿨어요



int main(int argc, char** argv)
{
    int M;
    cin >> N >> M;
    farm = new int *[N];
    farm_origin = new int*[N];
    visited_origin = new int*[N];
    visited = new int*[N];
    for(int i = 0; i < N; i++) {
        farm[i] = new int[N];
        farm_origin[i] = new int[N];
        visited[i] = new int[N];
        visited_origin[i] = new int[N];
        for(int j = 0; j < N; j++) {
            cin >> farm[i][j];
            farm_origin[i][j] = farm[i][j];
            visited[i][j] = 0;
            visited_origin[i][j] = 0;
        }
    } //여기는 벡터로 할걸 쪼끔 후회중
    vector<pair<int,int>> v = vector<pair<int,int>>();
    int sum = 0, tmp = 0;
    for(int i = 0; i < M; i++) {
        int X, Y;
        cin >> X >> Y;
        v.push_back(make_pair(X-1,Y-1));
    }
    do{
        for(auto iter:v) {
            tmp += bfs(iter.first,iter.second);
            while(check_max.size()) check_max.pop();
        }
        memcpy(farm,farm_origin,sizeof(int)*N*M);
        memcpy(visited,visited_origin,sizeof(int)*N*M);
        sum = max(tmp,sum);
        tmp = 0;


    } while(next_permutation(v.begin(),v.end()));
    cout << sum;
   return 0;
}

일단 깊이 재는 데 편하려고 DFS 썼고, 3 초과일때 탐색 빠꾸 먹여서 해봤는데...기본 예제 입력(테케1)만 맞고 다 틀리네요..어떤 부분에서 발상이 잘못된지 알려주세요..

소스는 다음과 같습니다..

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


using namespace std;
typedef pair<int,int> iter2dim;


iter2dim i2dim[4] = {
    make_pair(-1,0),
    make_pair( 1,0),
    make_pair(0,-1),
    make_pair(0, 1)
};
int N;


bool avail(int x, int y) {
    if(x<0 or y<0) return false;
    if(x>=N or y>=N) return false;
    return true;
}


void dfs(int ** &farm, int x, int y, int count, int &sum) {
    if(!avail(x,y)) return;
    if(farm[x][y] == 0) return;
    if(count >= 4) return;
    sum += farm[x][y];
    farm[x][y] = 0;
    int maxVal = 0, recurX = x, recurY = y;
    for(int i = 0; i < 4; i++) {
        int tmpX = x+i2dim[i].first, tmpY = y+i2dim[i].second;
        if(avail(tmpX,tmpY) && farm[tmpX][tmpY] > 0) {
            if(maxVal<farm[tmpX][tmpY]) {
                maxVal = farm[tmpX][tmpY];
                recurX = tmpX;
                recurY = tmpY;
            }
        }
    }
    if(recurX != x or recurY != y) dfs(farm,recurX,recurY,count+1,sum);
}




int main(int argc, char** argv)
{
    int M;
    cin >> N >> M;
    int **farm = new int *[N];
    for(int i = 0; i < N; i++) {
        farm[i] = new int[N];
        for(int j = 0; j < N; j++) {
            cin >> farm[i][j];
        }
    }
    vector<pair<int,int>> v;
    for(int i = 0 ; i < M; i++ ) {
        int X, Y;
        cin >> X >> Y;
        v.push_back(make_pair(X,Y));
    }
    int sum = 0, tmp = 0, answer = 0;
    do {
        for(auto itm:v) {
            tmp = 0;
            dfs(farm,itm.first-1,itm.second-1,0,tmp);
            sum += tmp;
        }
        if(sum>answer) answer = sum;
    } while(next_permutation(v.begin(),v.end()));
    cout << answer;
   return 0;
}

+이것도 틀렸네요,,,

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
constexpr int CNT = 3;
typedef pair<int,int> iter2dim;
vector<vector<int>> farm;
vector<vector<bool>> visited;
typedef pair<int,iter2dim> pth;
set<pth> path_visited;
iter2dim i2dim[4] = {
    make_pair(-1,0),
    make_pair( 1,0),
    make_pair(0,-1),
    make_pair(0, 1)
};
int N;
bool avail(int x, int y) {
    if(x<0 or y<0) return false;
    if(x>=N or y>=N) return false;
    return true;
}
void dfs(int x, int y, int count, int &sum) {
    if(!avail(x,y)) return;
    if(visited[x][y]) return;
    if(count > CNT) return;
    sum += farm[x][y];
    visited[x][y] = true;
    int maxVal = 0, recurX = x, recurY = y;
    for(int i = 0; i < 4; i++) {
        int tmpX = x+i2dim[i].first, tmpY = y+i2dim[i].second;
        if(avail(tmpX,tmpY) and !visited[tmpX][tmpY]) {
            if(maxVal<=farm[tmpX][tmpY]) {
                maxVal = farm[tmpX][tmpY];
                recurX = tmpX;
                recurY = tmpY;
            }
        }
    }
    pth p = make_pair(count,make_pair(recurX,recurY));
    if(path_visited.find(p) != path_visited.end()) {
        return;
    }
    path_visited.insert(p);
    if(count < CNT) dfs(recurX,recurY,count+1,sum);
    path_visited.erase(p);
}
int main(int argc, char** argv)
{
    int M;
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        farm.push_back(vector<int>());
        visited.push_back(vector<bool>());
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            int n;
            cin >> n;
            farm[i].push_back(n);
            visited[i].push_back(false);
        }
    }
    int sum = 0;
    vector<iter2dim> v;
    for(int i = 0; i < M; i++) {
        iter2dim iter;
        cin >> iter.first >> iter.second;
        iter.first--;
        iter.second--;
        v.push_back(iter);
    }
    do {
        int tmp = 0;
        for(auto i : v) {
            path_visited.insert(make_pair(0,make_pair(i.first,i.second)));
            dfs(i.first,i.second,0,tmp);
        }
        for(auto i : visited) {
            fill(i.begin(),i.end(),0);
        }
        if(tmp > sum) sum = tmp;
    } while(next_permutation(v.begin(),v.end()));
    cout << sum;
   return 0;
}