[G5] 백준 3980번 선발 명단 C++ 백트래킹, 브루트포스 알고리즘

리뷰

 

11명의 선수가 각 포지션의 최대 기량을 가질 수 있게 완전 탐색을 하는 문제

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

 

전역 변수

• lst : 각 선수의 포지션별 기량 정보를 저장할 정수형 2차원 배열
• v : 방문 처리를 위한 정수형 배열
• tc, ans : 테스트케이스 수를 저장할 tc, 각 테스트 케이스마다 정답을 저장하고 출력할 ans

 

함수

1. bt

void bt(int level, int sum)

 

1. 완전 탐색에 사용할 함수 매개변수 level = 재귀 단계, sum = 현재 단계까지의 기량의 합이다.
2. level은 재귀 단계이기도 하면서 현재 선수를 의미하기도 한다.
3. 따라서 level이 0일 경우엔 첫번째 선수의 11개 포지션에 대한 기량을 탐색한다.
4. 만약 0보다 클 경우 해당 선수를 해당 포지션에 배치하고 그 다음선수를 탐색하게 된다.
5. 재귀를 진행하기 전 방문처리를 해서 해당 포지션은 이미 배치되었다는 것을 명시해 주어야 한다.
6. 재귀가 끝난 뒤엔 해당 포지션을 방문 해제하여 다시 배치할 수 있음을 명시해 주어야 한다.

 

 

문제풀이

1. tc를 입력 받고 tc번의 반복문을 수행하여 테스트 각 케이스를 진행한다.
2. 각 테스트 케이스 마다 ans를 0으로 초기화 해주고 lst 배열에 11 * 11 크기의 데이터를 받아준다.
3. level = 0, sum = 0인 상태에서 bt함수를 실행하여 백트래킹을 시작한다.
4. ans에 저장된 값을 출력해 주고 줄바꿈을 해준다.

 

참고 사항

각 테케마다 ans를 0으로 초기화 해주어야 한다.

 

 

정답 코드

#include<iostream>

using namespace std;
int lst[11][11];
int v[11];
int tc, ans;

void bt(int level, int sum) {
	if (level == 11) {
		ans = max(ans, sum);
		return;
	}

	for (int i = 0; i < 11; i++) {
		if (v[i]) continue;
		if (!lst[level][i]) continue;
		v[i] = 1;
		bt(level + 1, sum + lst[level][i]);
		v[i] = 0;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> tc;
	while (tc--) {
		ans = 0;
		for (int i = 0; i < 11; i++) {
			for (int j = 0; j < 11; j++) {
				cin >> lst[i][j];
			}
		}
		bt(0, 0);
		cout << ans << "\n";
	}
}