[백준 18290] NM과 K (자바)

백준 18290번 NM과 K (자바)

 

 

출처

www.acmicpc.net/problem/18290

18290번: NM과 K (1)

 

 

 

 

문제

크기가 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

 

입출력 예 2

입출력 예 3

입출력 예 4

 

 

 

풀이 방법

1. 완전탐색(dfs + 백트래킹)으로 풀어야 한다.

2. go() 메서드를 통해 해당 원소의 주변 원소에 +1 해줘 방문할 수 없게 만든다.

3. 결과값 담을 배열에 현재 값을 넣는다.

4. 시작점+1 으로 재귀를 실행한다.

5. 시작점이 선택개수(k)와 같으면 출력 후 백트래킹으로 원상 복구한다.

 

 

 

내 코드

package brute_force;

import java.util.Scanner;

public class N_18290 {
   
   private static int n;
   private static int m;
   private static int k;
   
   private static int[][] array; //행렬
   private static int[][] cal; //인접 확인
   
   private static int[] list; //선택한 값 넣을 배열
   
   private static int max = -100000;
         
   public static void main(String[] args) {
      
      Scanner sc = new Scanner(System.in);
      
      n = sc.nextInt();
      m = sc.nextInt();
      k = sc.nextInt();
      
      list = new int[k];
      
      cal = new int[n][m];
      array = new int[n][m];
      for (int i=0; i<n; i++) {
         for (int j=0; j<m; j++) {
            array[i][j] = sc.nextInt();
         }
      }
      
      cycle(0);
      
      System.out.println(max);
      
   }

   private static void cycle(int start) {
      
      if (start == k) { //시작숫자가 K개일때 최대값 넣기
         int temp = 0;
         for (int i : list) {
            temp += i;
         }
         max = Math.max(max, temp);
      } else {
         
         for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
               if (cal[i][j] > 0) {
                  continue;
               }
               go(i, j); //인접 판별
               list[start] = array[i][j]; //현재값 넣기
               cycle(start+1); //재귀
               back(i, j); //원상복귀
            }
         }
         
      }
      
   }

   private static void go(int x, int y) {
      cal[x][y]++; //현재값 +1
      if (y-1 >= 0) {
         //위가 존재할때
         cal[x][y-1]++;
      }
      if (x-1 >= 0) {
         //왼쪽이 존재할때
         cal[x-1][y]++;
      }
      if (y+1 < m) {
         //아래가 존재할때
         //0,0일때 실행 -> 0,1
         cal[x][y+1]++;
      }
      if (x+1 < n) {
         //오른쪽이 존재할때
         //0,0일때 실행 -> 1,0
         cal[x+1][y]++;
      }
   }
   
   private static void back(int x, int y) {
      cal[x][y]--;
      if (y - 1 >= 0) {
         cal[x][y-1]--;
      }
      if (x - 1 >= 0) {
         cal[x-1][y]--;
      }
      if (y + 1 < m) {
         cal[x][y+1]--;
      }
      if (x + 1 < n) {
         cal[x+1][y]--;
      }
   }
}

 

 

고려할 점

1. dfs 사용할 것

2. 인접 원소 방문 못하게 처리

3. 백트래킹