[백트래킹] 백준 18290 NM과 K(1)

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

18290번: NM과 K (1)

수행시간 : 1시간 / 난이도 : 실버 1

 

DFS를 통한 재귀 + 재귀를 돌때마다 좌표를 통한 체크

이 2가지만 구현 할 수 있으면, 쉽게 풀리는 문제이다. 재귀를 도는 조건은 visited가 false 임과 동시에 선택한 칸들이 인접하면 안되므로

조합느낌으로 백트래킹을 구현하고, 백트래킹 내부 조건으로 인접했는지 아닌지를 판단해주면 되는 문제였다.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> v_map;
bool visited[11][11];
int n, m, k;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int max_val = -99999999;

void input() {
	cin >> n >> m >> k;
	v_map.resize(n, vector<int>(m));
	for (int i = 0;i < n;++i) {
		for (int j = 0;j < m;++j) {
			cin >> v_map[i][j];
		}
	}
}
bool no_injub(int x, int y) {
	for (int i = 0;i < 4;++i) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
			if (visited[nx][ny] == true) {
				return false;
			}
		}
	}
	return true;
}
void sol(int sum, int cnt) {
	if (cnt == k) {
		if (max_val < sum) {
			max_val = sum;
		}
		return;
	}

	for (int i = 0;i < n;++i) {
		for (int j = 0;j < m;++j) {
			if (visited[i][j] == false && no_injub(i, j) == true) {
				visited[i][j] = true;
				sol(sum + v_map[i][j], cnt + 1);
				visited[i][j] = false;
			}
		}
	}
}

int main() {
	input();
	sol(0, 0);
	cout << max_val;
}