[SWEA] 2112. 보호 필름 (Java)

 

문제

SW Expert Academy

 

알고리즘

구현, 완전탐색, 백트래킹

 

풀이

각 행은 약품 투입을 하지 않거나, A 약품을 투입하거나 B 약품을 투입하는 3가지 선택지가 있다.

경우의 수는 보호 필름의 두께(행의 수)는 최대 13이므로 3^13 = 약 160만 개이므로,

모든 경우의 수에 대해 완전 탐색하면서 유망하지 않은 경우는 가지 않는 백트래킹을 통해 시간을 단축한다.

 

유망하지 않은 경우는 현재 약품 투입 횟수가 지금까지 구한 약품 투입 횟수의 최솟값보다 크거나 같은 경우이다.

또 합격 기준이 K이면 연속된 K 줄에 같은 약품을 투입하면 무조건 검사에 통과할 수 있기 때문에 약품 투입 횟수의 최솟값은 K 부터 시작한다.

 

현재 약품 투약 횟수 count와 이번에 약품을 투입할 행의 index를 매개변수로 함수를 호출한다.

함수의 흐름은 다음과 같다.

static void dfs(int count, int index) {

	// 현재 투약 횟수가 최솟값보다 크거나 같다면 더 이상 진행할 필요없음
	if (count >= min) return;

	// 최솟값보다 작다면 성능 검사 통과 가능한지 확인 후 갱신
	if (index == D) {
		if (check()) min = count;
		return;
	}

	// 투약을 하지 않고 재귀 호출
	dfs(count, index + 1);

	// 투약하기 전 상태 복사
	int[] copyArr = new int[W];
	System.arraycopy(board[index], 0, copyArr, 0, W);

	// A와 B 투약 후 재귀 호출
	for (int i = 0; i < 2; i++) {
		Arrays.fill(board[index], i);
		dfs(count + 1, index + 1);
	}

	// 투약하기 전 상태 복원
	board[index] = copyArr;
}

 

성능 검사에 통과할 수 있는지 확인하는 check 함수는

문제에서 주어진 그대로 모든 행이 K개 이상 연속적인 셀을 가지고 있을 때 true를 반환하고 그렇지 않다면 false를 반환한다.

 

코드

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

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			board = new int[D][W];

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

			min = K;
			dfs(0, 0);

			sb.append("#").append(t).append(" ").append(min).append("\n");
		}
		
		System.out.println(sb);
	}

	static void dfs(int count, int index) {

		if (count >= min) return;

		if (index == D) {
			if (check()) min = count;
			return;
		}

		dfs(count, index + 1);

		int[] copyArr = new int[W];
		System.arraycopy(board[index], 0, copyArr, 0, W);

		for (int i = 0; i < 2; i++) {
			Arrays.fill(board[index], i);
			dfs(count + 1, index + 1);
		}

		board[index] = copyArr;

	}

	static boolean check() {

		label1: for (int x = 0; x < W; x++) {
			int max = 0;
			int cur = 1;
			for (int y = 1; y < D; y++) {
				cur = board[y][x] == board[y-1][x] ? cur + 1: 1;
				max = Math.max(max, cur);

				if (max >= K) continue label1;
			}

			return false;
		}
		return true;
	}
}