[swea] 2112번 / Java / 보호 필름

문제 

적당한 가지치기를 해야하는 dfs 문제였다

처음엔 완전탐색(부분집합)으로 풀었다

1. 두께별로 하나하나 방문해서 방문하고있는 위치를 전부 0, 1 (A, B)로 바꾼다.

2. 기저에 도달하면 완성된 필름을 검사하여 k만큼 연속되어있는지 확인한다

3. k만큼 연속되지 않은 것이 발견된다면 곧바로 검사를 종료하고, 전부 k만큼 연속되어있다면 주입한 약품의 수를 이용해 min값을 업데이트 한다.

---

🗝키포인트

• dfs진행 시, 현 시점에서 주입한 약품의 수가 min보다 크거나 같다면 더이상 탐색할 필요없이 최소가 될 수 없으므로 탐색을 하지 않도록 한다.
• min이 뭔데? 지금까지 필름을 완성해왔을 때, 사용했던 약품의 수 중 최솟값

 

---

코드

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

public class Solution {
	static int D, W, K;
	static int[][] map;
	static int min;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

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

		for (int test_case = 1; test_case <= TC; test_case++) {

			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[D][W];
			min = Integer.MAX_VALUE;
			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < W; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			dfs(0, 0);
			sb.append('#').append(test_case).append(' ').append(min == Integer.MAX_VALUE ? 0 : min).append('\n');
		}

		System.out.print(sb);
	}

	private static void dfs(int k, int cnt) {
		if (cnt >= min) // 최소값을 넘어가면 의미 없다!!!!!!!!
			return;
		
		if (k == D) {
			loop: for (int i = 0; i < W; i++) {
				int same = 1;
				for (int j = 0; j < D - 1; j++) {
					if (map[j][i] == map[j + 1][i]) {
						same++;
					} else {
						same = 1;
					}

					if (same >= K) {
						continue loop;// same == K를 한번이라도 발견하면 다음 열 검사
					}
				}
				return;// 다 돌았는데 same == K 였던 적이 없는 열이 있다면 불합격
			}
			min = Math.min(min, cnt);
			return;
		}

		int[] tmp = map[k].clone();

		// 투입 안하기
		dfs(k + 1, cnt);

		// A 약품 투입
		Arrays.fill(map[k], 0);
		dfs(k + 1, cnt + 1);

		// B 약품 투입
		Arrays.fill(map[k], 1);
		dfs(k + 1, cnt + 1);

		map[k] = tmp;
	}
}