[코테]06-NM과 K

NM과 K

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

• K개의 칸 -> 칸이 인접하면 안된다.

• 재귀함수를 이용

• ex) 100개 중에서 4개를 구한다. 100999897/4321

• 방법의 개수가 많지 않아서 모든 방법을 만들어도 됨.

• cnt : 선택한 칸의 개수

• sum : 선택한 칸의 합

• 기존칸과 인접하면 안되기 때문에 위,아래,왼,오 4방향 조건을 주어야함.

• 시간복잡도는 O(nm^k)

• n과m(2)에서 사용했던 start~n까지의 개념을 도입시킴.

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

• px : 이전에 선택 칸의 행 번호

• 하지만, 같은 행에서 중복된 선택을 할 수 있음. 따라서 py를 넣음.

• (px, py) : 이전 선택한 칸.

• px == x , y=py+1

• px>x, y=1

-n과 m방법을 그대로 이용.

• (r,c)는 r * M + c 로 나타낼 수 있음.

~~이해가 잘 안간다,,,ㅠㅠ 그래서 우선 코드를 보면서 차근차근 이해해봤다,,, ~~

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 max = -999999999;
		static int dx[] = {0,0,1,-1};
		static int dy[] = {1,-1,0,0};
		
		static void go(int px, int cnt, int sum) {
			if(cnt==k) {	//선택한 칸의 개수가 k와 같다면 max에 최대값을 넣어줌.
				if(max < sum) max = sum;
				return;
			}
			
			//px는 이전에 선택한 칸의 행 번호. 그 번호부터 n까지 for문
			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];
						
						//인접한 4가지 방향 조건, 인접했으면 false
						if(0 <= nx && nx < n && 0 <=ny && ny < m)
							if(c[nx][ny]) ok = false;
					}
				//인접하지 않았을 경우 true. 
				if(ok) {
					c[x][y] =true;
					go(x, cnt+1, sum+a[x][y]);
					//x는 현재의 칸의 행번호이지만 재귀함수로 넘어가게 되면 이전의 칸의 행번호가 됨.
					
					c[x][y] = false;	//함수의 호출을 미리 준비하는 것. 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(max);
		}


}