SWEA 2115번 [모의 SW 역량테스트] 벌꿀채취 C++ 백트래킹, 완전 탐색

리뷰

브루트포스와 백트래킹이 접목된 문제 재귀는 아직도 너무 어렵다..

 

문제 풀이

1. 각 테케마다 max_val을 0으로 초기화 해주고, 2차 배열을 받아와 준다.
2. 일꾼 1이 0, 0부터 시작하여 일꾼의 작업공간을 제외한 하위 작업공간에서 일꾼 2가 일을 하도록 시켜야 한다.
3. 우선 일꾼 1이 m크기만큼 벌통을 수집하여 팔았던 수익을 bt 함수로 부터 구해준 뒤 이를 dfs 함수에 인자로 전달한다.
4. dfs함수는 일꾼 1이 일했던 범위를 피해 일을 할 수 있는 나머지 부분에서 일을 해준다.
5. 일꾼 1이 일을 할때마다 bt 함수를 실행해 마찬가지로 벌통을 수집하여 판 수익을 구하고 max_val에 일꾼 1이 일한 값과 일꾼 2가 일한 값을 더해준 후 최대값을 지속적으로 갱신해 준다.
6. 모든 for문과 재귀가 종료되었을때 각 테케마다 max_val의 값을 출력해 주면 된다.

 

참고 사항

내가 짠 로직이 많이 비효율 적으로 보이긴 하는데 조건 범위를 보면 완전 탐색을 돌리는데에는 문제 없어 보였다.

1. main 함수에서는 일꾼 1이 일을 하고 (브루트 포스)
2. dfs 함수에서는 일꾼 2가 일을 한다. (브루트 포스)
3. bt 함수는 작업량에 대한 최대 가격을 완전 탐색으로 구해준다. (백트래킹)

일꾼 1이 이미 일했던 범위를 일꾼 2가 일을 하지 않게끔 중복을 제거해 준다.

bt함수를 호출할 때는 미리 max_temp와 방문 배열을 초기화 해줘야 한다.

for문이 많다 보니 변수명이 헷갈릴 수 있다. 로직이 맞는 것 같은데 틀린다면 해당 부분을 체크해 보자

 

정답 코드

#include<iostream>
#include<cstring>

using namespace std;

int tc, n, m, cc, max_val, max_temp;
int lst[11][11];
int temp[5];
int v[5];

void bt(int level, int val, int left) {
	if (level == m) {
		max_temp = max(max_temp, val);
		return;
	}

	for (int i = 0; i < m; i++) {
		if (!v[i] && left >= temp[i]) {
			v[i] = 1;
			bt(level + 1, val + (temp[i] * temp[i]), left - temp[i]);
			v[i] = 0;
		}
		else if (!v[i] && left < temp[i]) {
			v[i] = 1;
			bt(level + 1, val, left);
			v[i] = 0;
		}
	}
}

void dfs(int x, int y, int i1) {
	for (int i = x; i < n; i++) {
		for (int j = 0; j <= n - m; j++) {
			if (i == x && j < y + m) continue;
			for (int k = 0; k < m; k++) temp[k] = lst[i][j + k];
			memset(v, 0, sizeof(v));
			max_temp = 0;
			bt(0, 0, cc);
			max_val = max(max_val, max_temp + i1);
		}
	}
}

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

	cin >> tc;
	for (int c = 1; c <= tc; c++) {
		max_val = 0;
		cin >> n >> m >> cc;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> lst[i][j];
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= n - m; j++) {
				for (int k = 0; k < m; k++) temp[k] = lst[i][j + k];
				memset(v, 0, sizeof(v));
				max_temp = 0;
				bt(0, 0, cc);
				dfs(i, j, max_temp);
			}
		}
		cout << "#" << c << " " << max_val << "\n";
	}
}