[코딩테스트] 브루트 포스(NM과 K)

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

• N과 M은 재귀에 많이 사용되기 때문에 중요하다.
• 브루트 포스에 재귀로 풀 수 있는 문제
  1. 순서 : N가지 M개 뽑을 때 순서가 중요한 문제 O(N!)
  2. 선택 : N가지를 다 할 수 있는데 M개를 어떤 순서로 할지 O(2ⁿ)

NM과 K (18290번)

https://www.acmicpc.net/problem/18290

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

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

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

풀이

• N과 M은 1차원 문제라면 NM은 2차원. NM개 중에 최대 4개 100C₄ = 100x99x98x97/4x3x2x1 = 3,921,225가지

import java.util.*;

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

	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);
	}
	private static void go(int cnt, int sum) {
		// int cnt : 선택한 칸의 개수
		// int sum : 선택한 값의 합
		if(cnt==k) {
			if(ans<sum)
				ans = sum;
			return;
		}
		for(int x=0; x<n; x++) {
			for(int y=0; y<m; y++) {
				if(c[x][y]) {
					continue;
				}
				boolean ok = true; // 선택가능 true, 아니면 false
				for(int i=0; i<4; i++) {
					int nx = x+dx[i];
					int ny = y+dy[i];
					//인접한 4방향 검사
					if(0<=nx && nx<n && 0<=ny && ny<m) {
						// 인접한 칸이 문제 격자판 범위 안에 있고
						if(c[nx][ny]) // 그 칸을 선택한 적이 있으면
							ok = false; // 선택할 수 없다.
					}
				}
				if(ok) {
					c[x][y] = true;
					go(cnt+1, sum+a[x][y]);
					c[x][y] = false;
				}
			}
		}
	}
}

• 함수 호출 최대 4번, 각각 함수마다 nm 호출, O((NM)⁴) = 1억
• 위 풀이로는 선택한 칸이 같은데, 선택한 순서가 다른 방법을 여러 번 계산하게 된다. (중복선택)
• 중복선택을 피하기 위해선 N과 M 2번쨰에서 오름차순을 위해 start를 써줬듯이 얘도 비슷하게 활용. (2,5)를 구했다면 (1,1)~(2,5)까진 계산팔 필요가 없으므로 (2,6)~(N,M)까지만 계산. 선택한 칸의 행을 항상 오름차순으로 유지한다면 중복된 선택 피할 수 있음.

private static void go(int px, int cnt, int sum) { //px : prev_x 이전 선택칸 행번호
		if(cnt==k) {
			if(ans<sum)
				ans = sum;
			return;
		}
		for(int x=px; x<n; x++) { //x=px
			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]); //다음함수는 x번부터 검사하라
					c[x][y] = false;
				}
			}
		}
	}

• 같은 행에서 중복된 선택을 할 수 있다는 단점. (1,2) (2,1) 선택은 피했지만 (1,2)(1,5) 후에 (1,5)(1,2)는 못피함. 이걸 위해서 go에 int py를 추가해주자. px==x면 y=py+1, px>x면 y=1부터 시작
• 속도가 처음 코드 1628ms 에서 360ms로 훨씬 단축된다!
• 또는 (r,c)는 r x M + c로 나타낼 수도 있다. row-major-order(https://blog.naver.com/loveyou_a_a/222136576687 참고). 1차원으로 가정하고 문제해결. N과 M(2)와 같이 풀면 된다. (x,y 좌표를 지정할 때 x는 m으로 나눈 몫으로, y는 m으로 나눈 나머지로)