18290 NM과 K (1)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	3877	1143	657	25.938%

문제

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.

입력

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.

출력

선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.

제한

• 1 ≤ N, M ≤ 10
• 1 ≤ K ≤ min(4, N×M)
• 격자판에 들어있는 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
• 항상 K개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.

예제 입력 1

1 1 1
1

예제 출력 1

1

예제 입력 2

2 2 2
1 2
3 4

예제 출력 2

5

예제 입력 3

2 2 2
5 4
4 5

예제 출력 3

10

예제 입력 4

5 5 3
1 9 8 -2 0
-1 9 8 -3 0
-5 1 9 -1 0
0 0 0 9 8
9 9 9 0 0

예제 출력 4

27

코드

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

public class P_18290 {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] cond;
    static int[][] nums;
    static int[] elem;
    static int[][] visited;
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        cond = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        nums = new int[cond[0]][cond[1]];
        elem = new int[Math.min(4, cond[0]*cond[1])];
        visited = new int[cond[0]][cond[1]];
        for (int i = 0 ; i < cond[0]; i++) nums[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        find_sequence(0);

        bw.write(Integer.toString(max));
        bw.flush();
    }

    public static void find_sequence(int pos) {
        if (pos == cond[2]) {
            int res = 0;
            for (int num : elem) {
                res += num;
            }
            max = (max > res) ? max : res;
        }
        else {
            for (int i = 0; i < cond[0]; i++) {
                for (int j = 0; j < cond[1]; j++) {
                    if (visited[i][j] > 0)
                        continue;
                    check_adjacency(i, j);
                    elem[pos] = nums[i][j];
                    find_sequence(pos + 1);
                    return_adjacency(i, j);
                }
            }
        }
    }

    public static void check_adjacency(int i, int j) {
        visited[i][j]++;
        if (i > 0) visited[i - 1][j]++;
        if (i < cond[0] - 1) visited[i + 1][j]++;
        if (j > 0) visited[i][j - 1]++;
        if (j < cond[1] - 1) visited[i][j + 1]++;
    }

    public static void return_adjacency(int i, int j) {
        visited[i][j]--;
        if (i > 0) visited[i - 1][j]--;
        if (i < cond[0] - 1) visited[i + 1][j]--;
        if (j > 0) visited[i][j - 1]--;
        if (j < cond[1] - 1) visited[i][j + 1]--;
    }
}

코드 내용

백트래킹을 이용했는데 인접 여부를 저장하는 배열을 추가했다.
인접한 부분은 +1을 해주는데 boolean 배열이 아닌 int형 배열로 설정한 이유는 백트래킹을 이용하는 것이기 때문에 각각의 경우에 대해서 인접했다는 것을 모두 축적시켜둬야 하기 때문이다.
true였던 것을 false로 돌려놔버리면 백트래킹을 할 때 다른 조건이 망가질 수 있기 때문에 +1을 했고, 다시 돌아갈 때에는 -1을 해 주었다.