[백준] 3980-선발 명단(C++)

문제링크:www.acmicpc.net/problem/3980

3980번: 선발 명단

 

dfs문제입니다. 

 

전형적인 dfs문제입니다. 백트래킹에 속하는 이유는 문제조건중에서

 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

라는 조건을 수행해야하기 때문입니다.

 

 

일반적인 dfs 방식을 사용해서 구현했습니다.

 

 

 

아래는 정답코드입니다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t = 0, result = 0;
int arr[11][11] = { 0, };
bool visited[11];

void dfs(int cnt, int sum) {
	if (cnt == 11) {
		result = max(result, sum);
		return;
	}

	for (int i = 0; i < 11; i++) {
		if (arr[cnt][i] == 0)
			continue;
		if (visited[i] == 0) {
			visited[i] = 1;
			dfs(cnt + 1, sum + arr[cnt][i]);
			visited[i] = 0;
		}


	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> t;

	while (t--) {
		for (int i = 0; i < 11; i++)
			for (int j = 0; j < 11; j++)
				cin >> arr[i][j];
		memset(visited, 0, sizeof(visited));
		result = 0;
		dfs(0, 0);
		cout << result << "\n";
	}

}