[Baekjoon Online Judge] 18290 - NM과 K (1) / Java

https://www.acmicpc.net/problem/18290

18290번: NM과 K (1)

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

public class Main {

	static int N, M, K, answer = Integer.MIN_VALUE;
	static int[][] map;
	static boolean[][] visited;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	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];
		visited = new boolean[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());
			}
		}

		search(0, 0, 0, 0);
		System.out.println(answer);
	}

	private static void search(int cnt, int preR, int preC, int sum) {
		if (cnt == K) {
			answer = Math.max(answer, sum);
			return;
		}

		boolean notAdj;
		for (int i = preR; i < N; i++) {
			for (int j = (preR == i ? preC : 0); j < M; j++) {
				if (visited[i][j]) {
					continue;
				}

				notAdj = true;
				for (int dir = 0; dir < 4; dir++) {
					int nr = i + dr[dir];
					int nc = j + dc[dir];

					if ((nr >= 0 && nr < N && nc >= 0 && nc < M) && (visited[nr][nc])) {
						notAdj = false;
						break;
					}
				}

				if (notAdj) {
					visited[i][j] = true;
					search(cnt + 1, i, j, sum + map[i][j]);
					visited[i][j] = false;
				}
			}
		}
	}
}