문제1 ) 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개의 줄에 격자판에 들어있는 수가 주어진다.

출력

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

제한

1 ≤ N, M ≤ 10
1 ≤ K ≤ min(4, N×M)
격자판에 들어있는 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
항상 K개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.
예제 입력 1
1 1 1
1
예제 출력 1
1
예제 입력 2
2 2 2
1 2
3 4
예제 출력 2
5

풀이

• 칸에 정수가 하나씩 들어있는 N행 M열의 격자판에서 K개의 칸을 선택하는 문제
• 선택한 칸에 들어있는 수의 합을 최대로 하는 문제
• 1≤N,M≤10,1≤K≤min(4,N×M)

NxM개 중에서 K개를 선택하는 방법의 수 최댓값은 3,921,225 가지 이다.

import java.util.Scanner;
public class Main {
    static int[][] a = new int[10][10];
    static boolean[][] c = new boolean[10][10];
    static int n, m, k;
    static int ans = -2147483647;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static void go(int cnt, int sum) {
    	//cnt  선택한 칸의 개수
    	//sum 선택한 칸의 합
        if (cnt == k) { //선택한 칸의 개수가 k개가 되면
            if (ans < sum) ans = sum;
            return;
        }
        for (int x=0; x<n; x++) {
            for (int y=0; y<m; y++) {//a배열의 모든 행과열을 검사
                if (c[x][y]) continue; //중복인지 아닌지
                //선택할수 있는 후보이면 밑 부분 실행
                boolean ok = true;
                //기존 칸과 인접하면 안되기 때문에 4방향을 검사
                for (int i=0; i<4; i++) {
                	//dx와 dy에는 입점한 칸의 좌표 차이가 들어있다. 
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    if (0 <= nx && nx < n && 0 <= ny && ny < m) {//문제의 격자판 범위안에 있는지
                    	//그때 그칸의 선택한적이 있으면
                        if (c[nx][ny]) ok = false;
                        //ok=true 이면 선택 가능
                        //  =false이면 불가능
                    }
                }
                if (ok) {
                    c[x][y] = true;
                    go(cnt+1, sum+a[x][y]);
                    c[x][y] = false;
                }
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        go(0, 0);
        System.out.println(ans);
    }
}

• 이 방법은 O((NM)^K)이다.
->(10*10)^4 = 100^4 = 1억 -> 시간복잡도가 너무 크다
• 선택한 칸이 같은데, 선택한 순서가 다른 방법을 여러 번 계산하게 된다.
• 예를 들어, (1,2),(2,1),(3,4)를 선택한 후에 다시 (2,1),(1,2),(3,4)를 또 선택할 수 있다
->중복선택을 해결해야한다.
해결하기 위해서는 N과M(2)의 오름차순을 생각해야한다.

ex) (2,5)를 계산한다면 (1,1) ~ (2,5)는 계산할필요가 없고
(2,6) ~ (N,M) 범위만 검사하면 됨

-> 선택한 칸의 행을 항상 오름차순으로 유지한다면 중복된 선택을 피할 수 있다

import java.util.Scanner;
public class Main {
    static int[][] a = new int[10][10];
    static boolean[][] c = new boolean[10][10];
    static int n, m, k;
    static int ans = -2147483647;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static void go(int px, int cnt, int sum) {
    	//px는 prev_x(이전 x)의 약자, 이전 선택 칸의 행 번호
        if (cnt == k) {
            if (ans < sum) ans = sum;
            return;
        }
        //x=px로만 바꾸면 전 행은 검사를 안함
        for (int x=px; x<n; x++) {
            for (int y=0; y<m; y++) {
                if (c[x][y]) continue;
                boolean ok = true;
                for (int i=0; i<4; i++) {
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                        if (c[nx][ny]) ok = false;
                    }
                }
                if (ok) {
                    c[x][y] = true;
                    go(x, cnt+1, sum+a[x][y]);
                    c[x][y] = false;
                }
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        go(0, 0, 0);
        System.out.println(ans);
    }
}

• 하지만, 같은 행에서 중복된 선택을 할 수 있다.
• 앞 페이지 소스와 같은 (1,2),(2,1),(3,4)를 선택한 후에 다시 (2,1),(1,2),(3,4)를 또 선택하는
경우를 피할 수 있지만
• (1, 2), (1, 5), (3, 4)를 선택한 후에 (1,5),(1,2),(3,4)를 선택하는 경우를 피할 수 없다.

import java.util.*;
public class Main {
    static int[][] a = new int[10][10];
    static boolean[][] c = new boolean[10][10];
    static int n, m, k;
    static int ans = -2147483647;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static void go(int px, int py, int cnt, int sum) {
        if (cnt == k) {
            if (ans < sum) ans = sum;
            return;
        }
        for (int x=px; x<n; x++) {
            for (int y=(x == px ? py : 0); y<m; y++) {
                if (c[x][y]) continue;
                boolean ok = true;
                for (int i=0; i<4; i++) {
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                        if (c[nx][ny]) ok = false;
                    }
                }
                if (ok) {
                    c[x][y] = true;
                    go(x, y, cnt+1, sum+a[x][y]);
                    c[x][y] = false;
                }
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        go(0, 0, 0, 0);
        System.out.println(ans);
    }
}

여기서는 py도 추가
(px, py) = 이전에 선택한 칸
px == x 일 경우 y = py로 지정하면 됨

다른 방법

• (r,c)는 r×M +c 로 나타낼 수 있다.
• 이 점을 이용해서 구현할 수도 있다
(i,j)
ixM(열)+j

0 1 2 3
4 5 6 7
8 9 10 11

1차원이라고 가정하고 풀기
->이렇게 되면 N과M(2)와 같은 문제이다.

import java.util.*;
public class Main {
    static int[][] a = new int[10][10];
    static boolean[][] c = new boolean[10][10];
    static int n, m, k;
    static int ans = -2147483647;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static void go(int prev, int cnt, int sum) {
        if (cnt == k) {
            if (ans < sum) ans = sum;
            return;
        }
        for (int j=prev+1; j<n*m; j++) {
            int x = j/m;
            int y = j%m;
            if (c[x][y]) continue;
            boolean ok = true;
            for (int i=0; i<4; i++) {
                int nx = x+dx[i];
                int ny = y+dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (c[nx][ny]) ok = false;
                }
            }
            if (ok) {
                c[x][y] = true;
                go(x*m+y, cnt+1, sum+a[x][y]);
                c[x][y] = false;
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        go(-1, 0, 0);
        System.out.println(ans);
    }
}