[C++][백준] - NM과 K (1) (18290번)

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

18290번: NM과 K (1)

🔔 문제 : 

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

위와같은 제한 조건이 있는 N x M 격자판의 각 칸에 정수가 하나 들어있습니다. 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력하면 되는 문제입니다. 단 선택한 두 칸이 인접하면 안됩니다. 동서남북으로 인접한 칸이 선택을 못하게 됩니다.

---

🔔 Kick Point :

 

여기서 모든 경우의 수를 순열을 이용하여 선택을 하였습니다.

다만 추가된 조건으로 인접한 경우의 수는 선택 자체를 못하기 때문에 switchAdjacent인 함수를 통하여

변수 adjacent[MAX][MAX] 배열의 값이 0이면 선택가능하게 1 이상이면 인접한 수가 있는 경우의 수로 분류하고

최댓값 수를 구해갔습니다.

 

여기서 결과값인 변수 result의 초기값을 -1000000으로 둔 이유는 
NxM 격자판인 10x10의 최솟값이 10 * 10 * -10,000 = -1,000,000 이기 때문입니다.

 

---

🔔 Code :

 

 

#include <iostream>
using namespace std;

#define MAX 10

int arr[100] = {0, };

int grid[MAX][MAX];
bool visited[MAX][MAX] = { 0, };
int adjacent[MAX][MAX] = { 0, };

int n, m, k;
int result = -1000000;


void switchAdjacent(int n_ , int m_, bool toggle) {
	int k;
	if (toggle == true) k = 1;
	if (toggle == false) k = -1;

	if (n_ > 0) adjacent[n_ - 1][m_] += k;
	if (n_ < n - 1) adjacent[n_ + 1][m_] += k;
	if (m_ > 0) adjacent[n_][m_ - 1] += k;
	if (m_ < m - 1) adjacent[n_][m_ + 1] += k;
}



void dfs(int cnt = 0) {

	if (cnt == k) {
		int tmp = 0;
		for (int i = 0; i < k; i++) { 
			tmp += arr[i]; 
		
		}
		

		if (tmp > result) { result = tmp; }
		
		return;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {

			if (!visited[i][j] && !adjacent[i][j]) {
			visited[i][j] = true;

			switchAdjacent(i, j, true);
			arr[cnt] = grid[i][j];
			dfs(cnt + 1);

			visited[i][j] = false;
			switchAdjacent(i, j, false);
			}
		}
	}


}



int main() {

	cin >> n >> m >> k;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> grid[i][j];
		}
	}

	dfs();
	
	cout << result;
	
}

---