백준 18290번 : NM과 K (1)

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

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

public class Main {
    int result = Integer.MIN_VALUE;
    int[][] num;
    boolean[][] check;
    int n;
    int m;
    int k;
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    public void solution() 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());
        k = Integer.parseInt(st.nextToken());
        num = new int[n][m];
        check = new boolean[n][m];
        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<m; j++){
                num[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0,0,0,0);
        System.out.println(result);
    }

    public void dfs(int x, int y, int sum, int depth){
        if(depth == k){
            result = Math.max(sum, result);
            return;
        }
        for(int i = x; i<n; i++){
            for(int j = y; j<m; j++){
                if(!check[i][j]){
                    if(check(i, j)){
                        check[i][j] = true;
                        dfs(x,y, sum+num[i][j], depth+1);
                        check[i][j] = false;
                    }
                }
            }
        }
    }
    public boolean check(int x, int y){
        boolean flag = true;
        for(int i=0; i<4; i++){
            int currentX = x+dx[i];
            int currentY = y+dy[i];
            if(currentX>=0&&currentX<n&&currentY>=0&&currentY<m){
                if(check[currentX][currentY]){
                    flag = false;
                }
            }
        }
        return flag;
    }

    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

DFS와 백트래킹을 활용한다. 격자의 인덱스를 돌아 방문여부를 판단하고, 방문하지 않았고, 그 인덱스 동서남북이 방문한 적이 있는지 없는지를 체크(인접한 수) 없을시에 방문체크하고 다시 재귀... 체크 횟수가 K와 같아질때 가장 높은 값을 결과값에 저장 , 출력한다. 기본 값을 0으로 초기화 해놓을 경우, Math.max로는 격자가 모두 음수일 경우 가장 큰 숫자를 찾지 못하기 때문에 Math.MIN_VALUE로 초기화 해준다.