18290번: NM과 K (1)

문제

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 적혀 있습니다. 이 격자판에서 칸 K개를 선택하려고 합니다. 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하는 프로그램을 작성하는 문제입니다. 단, 선택한 두 칸이 인접하면 안 됩니다. (상하좌우로 붙어있는 칸은 인접한 칸으로 간주합니다.)

• 입력: 첫째 줄에 N, M, K가 주어집니다. (1 ≤ N, M ≤ 10, 1 ≤ K ≤ min(4, N×M)) 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어집니다. (각 수는 -10,000 이상 10,000 이하)
• 출력: 선택한 칸에 적힌 수를 모두 더한 값의 최댓값을 출력합니다.

풀이: 2차원 조합 탐색을 활용한 인접 방지 백트래킹

단순히 K개의 칸을 순열로 고르면 겹치는 조합이 너무 많아 시간 초과가 발생할 수 있습니다. 2차원 배열을 1차원처럼 취급하여, '이전에 고른 칸의 다음 칸'부터 탐색을 이어나가는 조합 방식으로 최적화해야 합니다.

• 음수 최댓값 대비: 선택된 칸들의 합이 음수가 될 수 있으므로 정답 변수 ans의 초기값은 Integer.MIN_VALUE로 설정해야 합니다. 
• 탐색 범위 최적화 (y, x):
  • 매개변수 y와 x는 직전에 선택한 칸의 행과 열 인덱스입니다.
  • 바깥쪽 반복문(i)은 y 행부터 끝까지 순회합니다.
  • 안쪽 반복문(j)은, 현재 행 i가 직전 행 y와 같다면 직전 열 x부터 탐색하고, 다음 행으로 넘어간 상태라면 처음(0)부터 탐색하도록 삼항 연산자 (i == y ? x : 0)를 사용하여 중복 탐색을 완벽히 차단합니다.
• 인접 조건 검사: 현재 칸 (i, j)를 선택하기 전에 상하좌우 4방향을 확인합니다. 범위를 벗어나지 않고 이미 선택된 칸(visited[ny][nx] == true)이 하나라도 있다면 flag = false 처리하여 해당 칸의 선택을 포기합니다.

코드

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

public class Main {
    static int n, m, k, ans = Integer.MIN_VALUE;
    static int[][] a;
    static boolean[][] visited;
    static int[] dy = { -1, 0, 1, 0 };
    static int[] dx = { 0, 1, 0, -1 };

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        a = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 방문 배열 할당 (NullPointerException 방지)
        visited = new boolean[n][m];

        // y, x 좌표와 깊이, 누적 합을 0으로 설정하여 시작
        go(0, 0, 0, 0);

        bw.write(ans + "");

        bw.flush();
    }

    // y, x: 탐색을 시작할 2차원 좌표, depth: 고른 칸의 수, sum: 누적 합
    static void go(int y, int x, int depth, int sum) {
        // K개를 모두 고른 경우 최댓값 갱신 후 반환 (기저 조건)
        if (depth == k) {
            ans = Math.max(ans, sum);
            return;
        }

        // 직전에 탐색했던 행(y)부터 시작
        for (int i = y; i < n; i++) {
            // 같은 행이면 x부터, 다음 행부터는 0번째 열부터 탐색 (중복 탐색 차단)
            for (int j = (i == y ? x : 0); j < m; j++) {
                if (visited[i][j]) {
                    continue;
                }

                boolean flag = true;
                // 상하좌우 인접한 칸이 이미 선택되었는지 검사
                for (int d = 0; d < 4; d++) {
                    int ny = i + dy[d];
                    int nx = j + dx[d];
                    if (ny >= n || nx >= m || ny < 0 || nx < 0)
                        continue;
                    if (visited[ny][nx]) {
                        flag = false;
                        break;
                    }
                }

                // 인접한 칸이 없다면 선택 후 다음 재귀로 이동
                if (flag) {
                    visited[i][j] = true;
                    go(i, j, depth + 1, sum + a[i][j]);
                    visited[i][j] = false; // 탐색 종료 후 원상 복구 (백트래킹)
                }
            }
        }
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force), 백트래킹 (Backtracking)