NM과 K (1)

📍 문제 설명

 

 

💡 접근

임의의 위치에서 인접한 위치를 제외하고 k번 선택후 합을 구하는 문제

 

1.중복 값이 더해지지 않도록 방문처리를 한다.

2.현재의 지점에서 갈 수 있는 인접한 지점에 방문처리가 안되어있을 때만 현 지점을 더한다.

 

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, k, answer = Integer.MIN_VALUE;
    static int[][] board;
    static int[] arr;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        k = kb.nextInt();
        board = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        visited = new boolean[n][m];
        T.solution(0, 0);
        System.out.println(answer);
    }

    private void solution(int L, int sum) {
        //숫자 k번 더했으면 최댓값 구해
        if(L == k) answer = Math.max(answer, sum);
        else {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    //방문 안했으면
                    if(!visited[i][j]) {
                        //인접한 지점 중 방문처리된 지점 있는지 확인
                        if(check(i, j)) {
                            visited[i][j] = true;
                            solution(L + 1, sum + board[i][j]);
                            visited[i][j] = false;
                        }
                    }
                }
            }
        }
    }

    //현 지점의 인접한 곳이 방문처리 - 현 지점 확인 할 수 없음
    private boolean check(int x, int y) {
        boolean flag = true;
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            //다음 지점이 갈 수 있는 지점인데 방문했으면 false
            if(nx>=0 && ny>=0 && nx<n && ny<m && visited[nx][ny]) flag = false;
        }
        return flag;
    }
}