[백준] 1566 - P배열

[문제링크]

1566번: P배열

0. reverseRow : 행을 뒤집고, rowSum/colSum을 갱신하는 함수

  - reverseCol : 열을 뒤집고, rowSum/colSum을 갱신하는 함수

  - toOrigin : 뒤집었던 열(t2변수에 bitmask로 저장됨)들을 복구하는 함수 

  - findmin : 부분집합을 만들고, 열을 뒤집고, 행을 검사하는 함수

 

1. 배열의 모든 행에 대해, 모든 가능한 부분집합을 만들어 reverse한다

 

2. 1번의 모든 경우에 대해, 값이 음수인 모든 열을 뒤집어본다

  - 값이 0인 열이 있다면 뒤집어도 0이므로, 양수가 될수 없으니 즉시 원상복귀 후 return한다

 

3. 2번을 통해 모든 열이 양수가 된 후에도 모든 행이 양수를 유지하고 있다면, 옳은 P배열이다

  - min값 갱신

 

4. min의 최댓값은 (N+M)/2이므로, (N+M)/2+1을 초깃값으로 정한다

  - ( N, M은 18 이하이므로 19 이상의 임의의 수를 사용해도 문제 없다 )

  - 동일한 값을 유지한다면 P배열을 만드는게 불가능했단 의미로, -1을 출력한다

  - 만드는게 가능했다면 구한 min값을 출력한다

 

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

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map=new int[N][M];
		rowSum = new int[N];
		colSum = new int[M];
		min=(N+M)/2+1;
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				colSum[j]+=map[i][j];
				rowSum[i]+=map[i][j];
			}
		}
		findmin(0, 0);
		
		if(min==(N+M)/2+1)System.out.println(-1);
		else System.out.println(min);
		
	}
	static int[] rowSum;//행 합계
	static int[] colSum;//열 합계
	static int[][]map;
	static int N,M,min;
	
	static void findmin(int cnt, int colChk) {
		if(cnt==M) {
			//행을 뒤집은 부분집합 완성
			int temp=0, temp2=0;
			for (int i = 0; i < N; i++) {
				if(rowSum[i]==0) {
					toOrigin(temp2);
					return;
				}
				else if(rowSum[i]<0) {
					reverserow(i);
					temp++;
					temp2 = temp2|1<<i;
				}
			}
			for (int i = 0; i < M; i++) {
				if(colSum[i]<=0) {
					toOrigin(temp2);
					return;
				}
			}
			min=min<colChk+temp?min:colChk+temp;
			toOrigin(temp2);
			
			return;
		}
		
		//안선택
		findmin(cnt+1,colChk);
		//선택
		reversecol(cnt);
		findmin(cnt+1,colChk+1);
		reversecol(cnt);
		
		
	}
	static void toOrigin(int t2) {
		for (int i = 0; i < N; i++)if((t2&1<<i)!=0)reverserow(i);
	}
	
	static void reverserow(int idx) {
		for (int i = 0; i < M; i++) {
			map[idx][i] =-map[idx][i];
			colSum[i] = colSum[i] +map[idx][i]*2; 
		}
		rowSum[idx]*=-1;
	}
	static void reversecol(int idx) {
		for (int i = 0; i < N; i++) {
			map[i][idx]=-map[i][idx];
			rowSum[i] = rowSum[i] +map[i][idx]*2; 
		}
		colSum[idx]*=-1;
	}
	
	
}

결과 화면