[SWEA]2112번:보호필름(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

• 알고리즘[풀이방법]

부분집합을 생성하는 백트래킹으로 풀었다. 3개 연속으로 같은 알파벳인지 확인하는 check메서드를 만들고, true를 리턴하면 그대로 cnt를 answer로 보내기. false가 나오면 부분 집합으로 약품을 첨가한다. cnt는 0이상, Depth미만의 값이어야 하고, answer가 true가 되었을 때의 최소 cnt를 값으로 반환한다.

---

package 김영서;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class S006_SWEA2112_보호필름 {
	static int D, W, K, arr[][], num;
	static boolean visited[];

	static void bt(int cnt, int idx, int[][] list) {
		boolean answer = false;
		answer = check(list);
		if (cnt >= 0 && cnt < D) {
			if (answer) {
				num = Math.min(num, cnt);
				return;
			}
		}

		// 변경할 줄 체크
		for (int i = idx; i < D; i++) {
			if (!visited[i]) {
				// i번째 줄 0으로 바꿔서 확인해보기1
				Arrays.fill(list[i], 0);
				visited[i]= true;
				bt(cnt + 1, i+1, list);
				for(int j=0;j<W;j++) {
					list[i][j] = arr[i][j];					
				}
				// i번째 줄 1으로 바꿔서 확인해보기
				Arrays.fill(list[i], 1);				
				bt(cnt+1, i + 1, list);
				for(int j=0;j<W;j++) {
					list[i][j] = arr[i][j];					
				}
				visited[i]=false;
			}
		}
	}

	static boolean check(int[][] list) {
		for (int j = 0; j < W; j++) {
			int cnt = 1;
			for (int i = 1; i < D; i++) {
				if (list[i][j] == list[i - 1][j]) {// 전 값이랑 같으면 cnt++
					cnt++;
				} else {// 다르면 초기화
					cnt = 1;
				}

				if (cnt >= K) {// cnt돌리는게 K보다 크거나 같으면 더 안봐도 된당!
					break;
				} // if
			} // for
			if (cnt < K) {// 한 줄 확인 다했는데 cnt가 K보다 작으면 이 경우는 실패
				return false;
			}
		} // for
		return true;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			num =Integer.MAX_VALUE;
			st = new StringTokenizer(br.readLine());
			D = Integer.parseInt(st.nextToken());// 6
			W = Integer.parseInt(st.nextToken());// 8
			K = Integer.parseInt(st.nextToken());// 3
			arr = new int[D][W];
			visited = new boolean[D];

			int[][]list = new int[D][W];
			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < W; j++) {
					int n =  Integer.parseInt(st.nextToken());
					arr[i][j] =n;
					list[i][j] =n;
				}
			}
//			System.out.println(Arrays.deepToString(arr));
			bt(0, 0, list);
			System.out.println("#" + tc + " " + num);
		}
	}
}