SWEA 2112번 [모의 SW 역량테스트] 보호 필름 C++ 재귀, 백트래킹

리뷰

접근하기 정말 힘든 문제였는데 SSAFY 강의를 듣고 재정리를 하여 통과하였다. 싸피 짱!

 

문제 풀이

1. 각 테스트 케이스 마다 약품 사용 횟수의 최소값, 현재 약품 사용 횟수, 약품 사용 여부 리스트를 초기화 해준다.
2. 보호필름 정보를 입력 받아 주고 재귀를 실행해 준다. 이때 전달해주는 매개변수는 row가 기준이 된다.
3. 약품을 사용하지 않은 케이스, A약품을 사용한 케이스, B약품을 사용한 케이스로 나누어 재귀를 실행한다.
4. 만약 약품을 사용하지 않았다면 path에 -1을 넣어주고, cnt를 증가하지 않는다.
5. 만약 약품을 사용했다면 path에 A약품은 0을, B약품은 1을 넣어주고 cnt를 1 증가시킨다.
6. 다음 row로 재귀를 실행해 주고 위에 적용했던 처리 조건들을 복구 해준다.
7. 만약 모든 행을 다 돌았다면 모든 칼럼에 0과 1이 연속 3개가 존재하는지 체크해 준다. 조건을 만족 한다면 사용한 약품의 개수 cnt를 ans와 비교하여 더 적다면 ans값을 cnt값으로 최신화 해준다.
8. 각 테스트 케이스에 대해 ans 값을 출력해 준다.

 

참고 사항

1. 모든 필름 배열에 세로로 같은 것이 연속적으로 K개 이상 존재해야 한다.
2. 약품을 투입하게 되면 해당 row가 전부 같은 특성으로 변한다.
3. 어느 층에 약품 사용 여부, 사용했다면 약품 정보를 기록해 줄 리스트가 필요하다.
4. 만약 재귀 진행 중 이미 cnt가 ans보다 크거나 같아졌을 경우 해당 케이스는 탐색할 필요가 없다. (가지치기)

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int t, d, w, k, cnt, ans;
int film[15][25];
vector<int> path;

void init() {
	cnt = 0;
	ans = 2121212121;
	path.clear();
	for (int i = 0; i < 15; i++) {
		for (int j = 0; j < 25; j++) {
			film[i][j] = 0;
		}
	}
}

void input() {
	// D : 두께, W : 가로 크기, K : 합격 기준
	cin >> d >> w >> k;
	for (int row = 0; row < d; row++) {
		for (int col = 0; col < w; col++) {
			cin >> film[row][col];
		}
	}
}

bool isValid() {
	// 지금 path대로 처리하면 합격/불합격 여부 체크
	for (int col = 0; col < w; col++) {
		// 세로 선을 하나 선택 
		int prev = film[0][col]; // 맨 윗줄의 특성 확인
		int cnt = 1; // 연속한 갯수
		int cnt_max = 1; // 연속한 갯수의 최대값
		if (path[0] != -1) prev = path[0];
		for (int row = 1; row < d; row++) {
			int nowValue = film[row][col];
			if (path[row] != -1) nowValue = path[row]; // 약품 투입이 기록되어 있는 대로 처리한다.
			if (prev == nowValue) cnt++;
			else cnt = 1;

			prev = nowValue;
			cnt_max = max(cnt_max, cnt);
		}
		if (cnt_max < k) return false;
	}
	return true;
}

void func(int now) {
	//기저
	if (now >= d) { // 0 ~ d - 1 필름 두께만큼 약품 투입 경우의 수 확인
		if (isValid()) ans = min(ans, cnt); // 이번에 뽑은 약품 대로 처리할 때 합격 기준에 부합하는가?
		return;
	}
	for (int i = -1; i <= 1; i++) { // i = -1 : 그대로, 0 : A약품 사용, 1 : B약품 사용
		//판별
		if (cnt >= ans) continue;
		//처리
		if (i != -1) cnt++;
		path.push_back(i);
		//재귀 호출
		func(now + 1);
		//복구
		if (i != -1) cnt--;
		path.pop_back();
	}
}

void solution() {
	func(0);
}

int main() {
	cin >> t;
	for (int c = 1; c <= t; c++) {
		init();
		input();
		solution();
		cout << "#" << c << " " << ans << "\n";
	}
}