백준 18290 : NM과 K(1) c++

코드

#include <iostream>

using namespace std;

int N, M, K;
int arr[11][11];
int ans = 0;
int max1 = -10001;
bool visited[11][11];

void dfs(int a, int b, int index){
	if(index == K){
		int sum = 0;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(visited[i][j])
				sum += arr[i][j];	
			}
		}
		if(sum >= max1) max1 = sum;
		return;
	}
	for(int i = a; i < N; i++){
		for(int j = 0; j < M; j++){
			if(!visited[i][j]){
				if(i >=1 && visited[i-1][j]) continue;
				if(j >=1 && visited[i][j-1]) continue;
				if(i < N-1 && visited[i+1][j]) continue;
				if(j < M-1 && visited[i][j+1]) continue;
				visited[i][j] = true;
				dfs(i, j, index+1);
				visited[i][j] = false;	
			}
		}
	}
	
}

int main(){
	
	cin >> N >> M >> K;
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> arr[i][j];
		}
	}
	dfs(0, 0, 0);
	
	cout << max1;
	
	return 0;
}

알게된 점

시간초과가 한번 났었다.

함수를 쓰면 확정적으로 종료될때 return을 쓰는 습관을 들이자

그리고 백트래킹 인제 진짜 알 것 같다.

굳