[Java] 18290 NM과 K

문제

문제
크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 
이 격자판에서 칸 K개를 선택할 것이고, 
선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다.

단, 선택한 두 칸이 인접하면 안된다. 
r행 c열에 있는 칸을 (r, c)라고 했을 때, 
(r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.

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

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

 

요약하면 K 개만큼 NxM 배열의 값 추출해서 더한 최대 값을 도출해야하는 문제이다.

브루트 포스 문제이다. 하지만 상하좌우로 인접한 값은 빼야한다는 조건이 존재하기 때문에 단순한 방식으로 찾기는 어렵다. 

 

dfs와 재귀를 활용하여 문제를 풀이한다.

DFS에 아직 능숙하지 못해 https://velog.io/@hyeokjinon/%EB%B0%B1%EC%A4%80-18290-NM%EA%B3%BC-K-java 블로그 글을 인용했다.

문제 풀이

1.NMK 값을 각각 받은 뒤 N,M 크기의 보드와 방문 체크용 boolean 배열을 생성한다.

2. 보드에 각 칸에 숫자를 입력받는다.

3. 0,0 자리부터 검색을 시작한다.

4. 우선 내가 고른 칸의 갯수가 k개와 같으면 그대로 종료한다.

5. 시작 인덱스를 기준으로 다음 칸부터 검사를 진행한다.

6. 만약 검사 중인 칸을 기준으로 인접한 칸에 이미 선택한 칸이 있다면 그대로 넘어간다.

7. 인접한 칸이 아닐 경우에 그 칸을 선택하고 고른 칸 + 1 해준 상태에서 해당 칸을 기준으로 다시 검사에 들어간다.(재귀)

 

자바 코드

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

public class NMK {
    private static int N, M, K, answer = Integer.MIN_VALUE;
    private static int[][] board;
    private static boolean[][] visited;
    private static final int[] dr = { -1, 1, 0, 0 };
    private static final 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());
        board = 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++) {
                // 격자판
                board[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) {
        // 숫자가 K개만큼 채워졌을시 값 리턴
        if (cnt == K) {
            answer = Math.max(answer, sum);
            return;
        }

        boolean notAdj;
        // preR : 시작 인덱스를 자신의 위치에서 시작
        for (int i = preR; i < N; i++) {
            for (int j = (preR == i ? preC : 0); j < M; j++) {
                // 자기자신이 이미 true일 경우 다음으로 이동
                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;
                    }
                }

                // notAdj = true일시 인접하지 않는 숫자이므로,
                // 해당 map[i][j] 값을 더함
                if (notAdj) {
                    visited[i][j] = true;
                    search(cnt + 1, i, j, sum + board[i][j]);
                    visited[i][j] = false;
                }
            }
        }
    }
}