문제

풀이 과정

단순 브루트포스 문제, 전체 배열 가운데 K 개 만큼의 조합을 만든다. 단 조합으로 뽑힌 모든 경우의 좌표들은 서로 인접하지 않아야 한다. 서로 인접한 배열 조건을 찾는 것은 다음 식으로 해결하였다.
$|nR-r| + |nC-c| <= 1$

r은 배열의 이전 y좌표, c는 배열의 이전 x좌표
nR은 현재 y좌표, nC는 현재 x좌표 이다.

이후, 각 좌표를 출발점으로 하여, 조합을 탐색하니 답이 나왔다.

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[][] map;
    static int N, M, K;
    static int ans = -40001;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] sel = new int[K][2];
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < 2; j++) {
                sel[i][j] = -1;
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sel[0][0] = i;
                sel[0][1] = j;
                comb(i, j, 1, map[i][j], sel);
                sel[0][0] = -1;
                sel[0][1] = -1;
            }
        }
        System.out.println(ans);
    }

    private static void comb(int r, int c, int cnt, int sum, int[][] sel) {
        if (cnt >= K) {
            ans = Math.max(sum, ans);
            return;
        }

        for (int i = r; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (Math.abs(i - r) + Math.abs(j - c) <= 1) continue;
                if (check(sel, i, j)) continue;
                sel[cnt][0] = i;
                sel[cnt][1] = j;
                comb(i, j, cnt + 1, sum + map[i][j], sel);
                sel[cnt][0] = -1;
                sel[cnt][1] = -1;
            }
        }
    }

    private static boolean check(int[][] sel, int r, int c) {
        for (int i = 0; i < K; i++) {
            if (sel[i][0] == -1) continue;
            if (Math.abs(sel[i][0] - r) + Math.abs(sel[i][1] - c) <= 1) return true;
        }
        return false;
    }
}

번외로, 스터디 팀원이 짠 코드가 괜찮아서 가져와봤다.
풀이는 굉장히 단순한편. 조합인 건 비슷하지만, 반복문 특성상, 무조건 좌표는 계속 증가하니, 이전의 값만 방문처리를 해주면 된다는 것이다.

```java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[][] map;
    static int N, M, K;
    static int ans = -40001;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] sel = new int[K][2];
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < 2; j++) {
                sel[i][j] = -1;
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sel[0][0] = i;
                sel[0][1] = j;
                comb(i, j, 1, map[i][j], sel);
                sel[0][0] = -1;
                sel[0][1] = -1;
            }
        }
        System.out.println(ans);
    }

    private static void comb(int r, int c, int cnt, int sum, int[][] sel) {
        if (cnt >= K) {
            ans = Math.max(sum, ans);
            return;
        }

        for (int i = r; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (Math.abs(i - r) + Math.abs(j - c) <= 1) continue;
                if (check(sel, i, j)) continue;
                sel[cnt][0] = i;
                sel[cnt][1] = j;
                comb(i, j, cnt + 1, sum + map[i][j], sel);
                sel[cnt][0] = -1;
                sel[cnt][1] = -1;
            }
        }
    }

    private static boolean check(int[][] sel, int r, int c) {
        for (int i = 0; i < K; i++) {
            if (sel[i][0] == -1) continue;
            if (Math.abs(sel[i][0] - r) + Math.abs(sel[i][1] - c) <= 1) return true;
        }
        return false;
    }
}