보호 필름

Brute Force, dfs, 재 문제는 필요 없는 부분을 빠르게 솎아내는 백트래킹이 중요하다는 것을 알려주는 문제라고 생각한다. =>조건 검사 메서드 구현, 리팩토링을 통한 중복 코드 삭제⭐️⭐️⭐️⭐️⭐️

Solution

• 조건 검사 메서드

1. 기능 : r번째 행 값이 연속해서 K개 이상이여야한다. 갯수cnt는 K개 이상이여야한다. cnt는 1부터 시작해야한다. 비교할 값 type과 temp[i][j]와 비교한다. 비교할 값 type은 각 행마다 temp[0][j]으로 시작한다. ⭐️⭐️⭐️⭐️⭐️ type과 배열 값이 다르다면 type은 그 값으로 갱신되고, cnt=1부터 다시 시작한다.

2. 리팩토링 : isPass()는 모든 경우의 수 연산하는 재귀함수 solve() ①호출 이전과, ②재귀함수에서 모든 순열 만들었을 때 ①과 ② 두가지 경우 호출된다. ②에서 검사를 하는 대상은 temp 배열이다. 그런데 ①에서는 원래의 배열 Film을 넣어야할 것 같아서 매개변수를 따로 생성했는데 애초에 Film과 똑.같.은 temp를 입력받을 때부터 저장해서 만들었기 때문에 결국 ①, ② 두가지 경우 모두 temp배열에 대해 검사를 하면 되므로 매개변수를 따로 받지 않고 그냥 함수 내부에서 temp 배열로 구현하면 된다.

3. 백트랙킹 : r번 행마다 같은지 조건 검사를 하다가 K개를 만족하는 순간 더 이상 비교할 필요가 없기 때문에 break문으로 행 반복문을 탈출해야한다!!!

private static boolean isPass() {
		for(int c = 0 ; c < W ; ++c) {
			int cnt = 1;int type = temp[0][c];boolean flag = false;
			for(int r = 1 ; r < D ; ++r) {
				if(type == temp[r][c]) {cnt++;} else {
					type = temp[r][c];cnt = 1;
				}
				
				if(cnt == K) {flag = true;break;}
			}
			if(!flag) return false;
		}
		
		return true;
	}

정답 솔루션과 비교 : 재귀를 이용한 Brute Force(dfs) 풀이 방법은 맞다. 하지만, 배열을 어떤 식으로 변형해서 재귀호출&실행& 원복하는지가 관건이다.

배열을 2개 사용하는 방법 원래 배열과 동일한 배열을 하나 더 생성하여 입력받을 때부터 값 저장

약품A로 재귀함수 호출&실행한 뒤 리턴됐을 때, 따로 원복시켜야한다고 생각해서 매개변수로 별도로 변형시킨 배열을 전달했는데 아래 정답 코드처럼 배열 값에 덮어쓰는 형식으로 약품B 재귀함수 실행시키고, 3가지 선택 다한 후에, 원래 배열 값을 넣어줌으로써 원복처리가 가능하다.

2차원 배열을 변형시키고, 변형한 배열을 다음 재귀함수로 넘기는 거라서 원복시키는 것도 굉장히 어렵게 생각했는데 그냥 배열 값에 새로운 값 덮어쓰고 원래 값 다시 셋팅해주면 되는 것이였다...

// 주입하지 않음
		injection(cnt, layer + 1);
		
		// A 주입
		for(int c = 0 ; c < W ; ++c) temp[layer][c] = 0;
		injection(cnt + 1, layer + 1);

		// B 주입
		for(int c = 0 ; c < W ; ++c) temp[layer][c] = 1;
		injection(cnt + 1, layer + 1);
		
		// 되돌리기 
		for(int c = 0 ; c < W ; ++c) temp[layer][c] = map[layer][c];

실제 재귀함수를 구현한 코드는 아래처럼 굉장히 짧다. 다만, 약품 A 또는 B를 주입하는 처리를 좀 신경써줘야한다.

private static void injection(int cnt, int layer) {
		if(cnt >= ans) return;
		
		if(layer == D) {
			if(isPass()) {
				ans = ans > cnt ? cnt : ans;
			}
			return;
		}
		
		injection(cnt, layer + 1);
		// A 주입
		for(int c = 0 ; c < W ; ++c) temp[layer][c] = 0;
		injection(cnt + 1, layer + 1);
		// B 주입
		for(int c = 0 ; c < W ; ++c) temp[layer][c] = 1;
		injection(cnt + 1, layer + 1);
		// 되돌리기 
		for(int c = 0 ; c < W ; ++c) temp[layer][c] = map[layer][c];
	}