2112. [모의 SW 역량테스트] 보호 필름

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.StringTokenizer;

class Solution {

static int knum, depth, Width;

static int[][] data;

static boolean Converse;

private static int Result;

private static boolean Debug = false;

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

BufferedReader br;

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

StringTokenizer st;

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

for (int T = 1; T <= TestNo; T++) {

st = new StringTokenizer(br.readLine());

// 문제 읽기

depth = Integer.parseInt(st.nextToken());

Width = Integer.parseInt(st.nextToken());

knum = Integer.parseInt(st.nextToken());

data = new int[depth][];

// 데이터 읽기

for (int i = 0; i < depth; i++) {

data[i] = new int[Width];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < Width; j++) {

data[i][j] = Integer.parseInt(st.nextToken());

}

}

Result = -1;

if (isOkay()) { // 원형 그대로 두어도 Okay

Result = 0;

}

for (int i = 1; i <= knum; i++) { // i개의 행에 약물 주입

if (Result >= 0) {

break; // 찾았으면 종료

}

visitingList = new ArrayList<>(); // 중복검색 방지

possibleList = new ArrayList<Integer>(); // 1이 i개인 이진수 탐색

int con_i = i > Width / 2 ? Width - i : i;

Converse = i > Width / 2;

findPossible(con_i, 0); // 1이 i개인 이진수 탐색

for (int j = 0; j < possibleList.size(); j++) {

log(Integer.toBinaryString(possibleList.get(j)));

Result = inputMedi(possibleList.get(j)); // (약물 주입) 행들의 집합을 넘긴다.

if (Result > 0) {

break; // 찾았으면 종료

}

}

}

System.out.println(String.format("#%d %d", T, Result));

}

}

static ArrayList<Integer> possibleList;

static ArrayList<Integer> visitingList;

// width개 중 i개를 선택한다.

private static void findPossible(int i, int bitinfo) {

if (bitinfo >= (1 << depth + 1)) {

return;

}

int count = 0;

for (int j = 0; j < depth; j++) {

if ((bitinfo & (1 << j)) > 0) {

count++;

if (count == i) {

log(Integer.toBinaryString(bitinfo));

possibleList.add(bitinfo);

return;

}

}

}

for (int j = 0; j < depth; j++) {

if ((bitinfo & (1 << j)) > 0) {

continue;

}

int next_bitinfo = bitinfo + (1 << j);

if (visitingList.contains(next_bitinfo)) {

continue;

}

visitingList.add(next_bitinfo);

findPossible(i, next_bitinfo);

}

}

public static int inputMedi(int selbit) {

ArrayList<Integer> pocket = new ArrayList<Integer>();

// 사용되는 열 추출

int con_selbit = selbit;

if (Converse) {

con_selbit = 0;

for (int i = 0; i < Width; i++) {

if ((selbit & (1 << i)) == 0) {

con_selbit += (1 << i);

}

}

}

for (int i = 0; i < Width; i++) {

if ((con_selbit & (1 << i)) > 0) {

pocket.add(i);

}

}

// boolean isFound;

int size = pocket.size();

// 1,0의 적용의 경우의 수

for (int i = 0; i < 1 << size; i++) {

// log(Integer.toBinaryString(i));

if (isOkay(i, pocket)) {

return pocket.size();

}

}

return -1;

}

private static boolean isOkay(int bitmask, ArrayList<Integer> pocket) {

int depth = data.length;

int width = data[0].length;

int a_count;

int b_count;

for (int i = 0; i < width; i++) {

a_count = b_count = 0;

int atom;

for (int j = 0; j < depth; j++) { // 한 열을 검사

atom = data[j][i];

if (pocket.indexOf(j) >= 0) {

boolean isOne = (bitmask & (1 << pocket.indexOf(j))) > 0;

atom = isOne ? 1 : 0;

}

if (atom == 1) {

if (b_count != 0) {

a_count = b_count = 0;

}

a_count++;

} else {

if (a_count != 0) {

a_count = b_count = 0;

}

b_count++;

}

if (a_count == knum || b_count == knum) {

break;

}

if (j == depth - 1) {

return false;

}

}

}

log(Integer.toBinaryString(bitmask) + pocket.toString());

return true;

}

private static boolean isOkay() {

int depth = data.length;

int width = data[0].length;

int a_count;

int b_count;

for (int i = 0; i < width; i++) {

a_count = b_count = 0;

for (int j = 0; j < depth; j++) { // 한 열을 검사

if (data[j][i] == 1) {

if (b_count != 0) {

a_count = b_count = 0;

}

a_count++;

} else {

if (a_count != 0) {

a_count = b_count = 0;

}

b_count++;

}

if (a_count == knum || b_count == knum) {

break;

}

if (j == depth - 1) {

return false;

}

}

}

return true;

}

private static void log(String input) {

if (Debug) {

System.out.println(input);

}

}

}