2112 보호필름

 

 

전략

1. 약품처리 K를 사용하는 경우의 수를 중복순열을 사용하여 3가지로 정의함.

(-1 : 아무것도 하지 않음)

( 0 : A 약품)

( 1 : B 약품)

 

2. check 함수를 어떤식으로 구현할까 고민했지만, 탐색을 위한 특별한 전략이 없다고 판단 BF로 진행.

문제 조건을 살펴보면, worst cast의 실행횟수는

 

3^13 * D*W = 3   ^   13   ×   13   ×   20 = 414,523,980

 

정도이며 실행시간이 5초 이내임을 감안하면 충분하다 판단함.

 

3. check 구현시, map을 직접 수정하면 원래대로 되돌리는 것이 번거롭기 때문에 dummy를 생성하여 사용후 버림.

 

 

완성 후 다음 사이트와 비교하여, 구현상의 차이점 정도를 살펴보면 좋을듯 싶다.

https://velog.io/@hyeon930/SWEA-2112-%EB%B3%B4%ED%98%B8-%ED%95%84%EB%A6%84-Java

 

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


class Solution {

	static int D, W, K;
	static int[][] skin, dummy;
	private static boolean DBG = false;

	static int min;

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T;
		T = Integer.parseInt(br.readLine());

		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {

			st = new StringTokenizer(br.readLine());
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			skin = new int[D][W];
			dummy = new int[D][W];
			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < W; j++) {
					skin[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			// index, cnt
			// 중복 순열
			min=Integer.MAX_VALUE;
			go(0, 0, new int[D]);

			System.out.println("#" + test_case + " " +min);

		}

		System.out.println(sb);

	}

	private static void go(int level, int cnt, int[] perm) {

		if (level == D) {
			if (cnt > K) {
				return;
			}
			StringBuilder sb = new StringBuilder();

			if (DBG) {
				sb.append("perm : \n");
				for (int v : perm)
					sb.append(v).append(' ');
				// System.out.println(sb);
				sb.append('\n');
			}
			// i, perm[i] => map's row , value
			int ii = 0;
			for (int[] ar : skin)
				dummy[ii++] = Arrays.copyOf(ar, ar.length);

			for (int i = 0; i < perm.length; i++) {
				int value = perm[i];
				if (value == -1)
					continue;
				Arrays.fill(dummy[i], value);
			}

			if (DBG) {
				sb.append("dummy : \n");
				for (int[] ar : dummy) {
					for (int v : ar) {

						sb.append(v).append(' ');
					}
					sb.append('\n');
				}
				System.out.println(sb);
			}

			if (check() == true) {
				//System.out.println("pass!");
				min = Math.min(min, cnt);
			} else {
				//System.out.println("NG!");
			}
			
			return;
		}
		// 중복 순열
		for (int i = -1; i < 2; i++) {
			perm[level] = i;
			cnt = (i == -1) ? cnt : cnt + 1;
			go(level + 1, cnt, perm);
			cnt = (i == -1) ? cnt : cnt - 1;
		}

	}

	private static boolean check() {
		boolean result = true;
				
		for ( int i = 0 ; i < W ; i++) {
			int cnt = 1;
			for (int j = 1 ; j < D ; j++) {
				if( dummy[j-1][i] == dummy[j][i])
					cnt++;	
				else 
					cnt = 1;	
				if (cnt >= K) break;
			}
			if( cnt < K)
				return false;			
		}	
		return result;
	}

}