소프티어

import java.io.*;
import java.util.*;


public class Main {
    static int n, m;
    static int[][] graph, count;
    static boolean[][] visited;
    static Friend[] friendArr;
    static int[] dx = new int[] {0, 0, 1, -1};
    static int[] dy = new int[] {1, -1, 0, 0};
    static int ans = 0;


    static class Friend {
        int row, col, value;


        Friend(int row, int col, int value) {
            this.row = row;
            this.col = col;
            this.value = value;
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
    
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());


        graph = new int[n][n];
        visited = new boolean[n][n];
        friendArr = new Friend[m];
        count = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());


            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());


            int row = Integer.parseInt(st.nextToken()) - 1;
            int col = Integer.parseInt(st.nextToken()) - 1;


            visited[row][col] = true;
            friendArr[i] = new Friend(row, col, graph[row][col]);
            count[row][col] = 1;
            
        }


        backtracking(0);
        System.out.println(ans);
    }


    static void backtracking(int cnt) {
        int total = 0;
        for (Friend f : friendArr) total += f.value;


        ans = Math.max(ans, total);
        
        if (cnt == 3*m) {
            return;
        }
        
        int idx = cnt % m;
        Friend cur_friend = friendArr[idx];
        boolean isflg = false;
        
        for (int i = 0; i < 4; i++) {
            int new_row = cur_friend.row + dy[i];
            int new_col = cur_friend.col + dx[i];
            
            if (new_row < 0 || new_row == n || new_col < 0 || new_col == n || isMeet(new_row, new_col)) continue;
            
            int value = 0;
            if (count[new_row][new_col] == 0) value = graph[new_row][new_col];
            
            count[new_row][new_col]++;
            cur_friend.row = new_row;
            cur_friend.col = new_col;
            cur_friend.value += value;
            
            backtracking(cnt+1);
            


            count[new_row][new_col]--;


            cur_friend.row -= dy[i];
            cur_friend.col -= dx[i];
            cur_friend.value -= value;


            isflg = true;
        }


        if (!isflg) backtracking(cnt+1);
    }


    static boolean isMeet(int new_row, int new_col) {
        for(Friend f : friendArr) {
            if (f.row == new_row && f.col == new_col) return true;
        }
        return false;
    }
}

아무리 코드를 바꿔봐도 마지막 테스트 케이스에서 걸리길래

다른 분들의 정답 코드를 넣었는데도 마지막 테스트 케이스에서 오류가 발생합니다.

마지막 테스트 케이스 수정 부탁드립니다.

그리고

테스트케이스

6 2

20 26 185 80 1 1

100 20 25 80 189 51

20 20 88 99 1 1

15 32 44 50 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 2

2 3

일 때

정답 644 아닌가요??

 한 나무에 여러 친구가 방문하게 되더라도 열매는 딱 한 번만 수확이 가능합니다. 이때, 친구들끼리 이동하는 도중 동시에 같은 사과나무에서 마주치는 경우에는 싸움이 일어날 수 있기 때문에 남우는 이와 같은 경우가 없기를 바랍니다.

=> 제가 이해한 바로는 한 나무에 여러 친구가 방문할 수 있지만, 동시에 만나면 안된다라고 이해를 했습니다.

그렇다면 위 테스트케이스에서

1)

첫 번째 친구) 26 -> 185 (135 획득, 총 211)

두 번째 친구) 25 -> 80 (80 획득, 총 105)

2)

첫 번째 친구) 185 -> 25 (0 획득, 총 211) / 1 단계에서 두 번째 친구가 획득

두 번째 친구) 80 -> 189 (189 획득, 총 294)

3)

첫 번째 친구) 25 -> 88 (88 획득, 총 299)

두 번째 친구) 189 -> 51 (51획득, 총 345)

결국 299 + 345 = 644 입니다.

3 단계 모두 동시에 마주친 적이 없지만 이 답이 아니라고 합니다.

제가 느끼기에는 문제 설명이 모호하다고 생각합니다.