[백준] 1080 행렬 - 그리디(탐욕법, Greedy) + 구현 + 비트마스크(BitMask) JAVA

https://www.acmicpc.net/problem/1080

1080번: 행렬

코드설명

그리디와 구현 문제입니다.

 

 

먼저 문제를 마주하면, 당연히 완전탐색이 떠오릅니다.

완전탐색일 경우 왜 안될까요? 시간초과가 발생합니다.

완전탐색을 할경우 시간복잡도는 2^(50 - 3) * (50 - 3) 입니다. 이는 10^14 이상의 연산횟수입니다.

 

그러면 어떻게 해야할까요? 바로 순서를 강제해야 합니다. 즉 가장 최상단좌측만 고려해주는 것이지요.

가장 최좌측상단의 것만을 확정시킬경우의 시간복잡도는 (50-3)*(50-3) 안에 해결됩니다.

처음에 실수했던점은, 가장 최좌측 상단의 것을 확정시킬때도 똑같이 시간복잡도가 2^(50-3)*(50-3)이나올것같다고 예상했으나 잘못된 생각이었습니다. 이유는 비교할 행렬 B가 존재하기 때문입니다. 

만약 비교할 행렬이 존재하지 않았다면 똑같이 시간복잡도 초과가 발생하겠지만, 이문제의 경우 비교대상인 행렬 B가 존재하므로 47*47 개의 연산안에 끝낼 수 있습니다.

 

그리디적으로 접근해보면, 

matrix[i][j] != matrixTarget[i][j] 라면 바로바로 3x3 행렬의 모든 행렬을 바꿔주는 연산을 진행해야합니다.

왜 이렇게 하는것이 최소의 연산 횟수가 나오는지 의문이 생깁니다.

이유는, 3*3 행렬이 이동하면서, 이미 뒤집은 요소는 다시는 뒤집지 않기에 최소 연산횟수가 나옵니다.

이러한 그리디적인 접근이 이 문제의 핵심입니다.

코드

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

public class Main {
	
	public static int N, M;
	public static int answer = 0;
	public static char[][] matrix;
	public static char[][] matrixTarget;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	matrix = new char[N][M];
    	matrixTarget = new char[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		matrix[i] = st.nextToken().toCharArray();
    	}
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		matrixTarget[i] = st.nextToken().toCharArray();
    	}

    	for(int i=0;i<N-2;i++) {
    		for(int j=0;j<M-2;j++) {
    			
    			if(matrix[i][j] == matrixTarget[i][j]) { //같으면 무시하고 넘어갑니다.
    				continue;
    			}
    			
    			for(int r=i; r< i+3; r++) {
    				for(int c=j; c< j+3; c++) {
    					matrix[r][c] = (matrix[r][c] == '1' ? '0' : '1');
    				}
    			}
    			answer += 1;
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(matrix[i][j] != matrixTarget[i][j]) {
    				System.out.println("-1");
    				return ;
    			}
    		}
    	}
    	
    	System.out.println(answer);
    }
    
}

 

비트연산 활용한 코드입니다.유의사항은 NOT 연산을 통해 뒤집어서 해당 칸의 1을 0 으로, 0을 1으로 바꿔주는데

32비트 자료형 int 연산을 사용하면, 모든 비트가 뒤집어집니다.(이는 부호비트까지 뒤집습니다.)

그렇기에 ~matrix[i][j] & 1 로 뒤집은 것의 가장 맨 앞 숫자만 고려함으로써 올바르게 비트연산을 사용합니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, R;
	static int answer = 0;
	static int[][] matrixA;
	static int[][] matrixB;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		matrixA = new int[N][M];
		matrixB = new int[N][M];
		
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for(int j=0;j<str.length(); j++) {
				matrixA[i][j] = str.charAt(j) - '0';
			}
		}
		
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for(int j=0;j<str.length(); j++) {
				matrixB[i][j] = str.charAt(j) - '0';
			}
		}
		
		answer = solve();
		System.out.println(answer);
		
	}
	
	static int solve() {
		int ret = 0;
		for(int i=0;i<N-3 + 1; i++){
			for(int j=0;j<M-3 + 1; j++) {
				//만약 XOR 연산을 했을떄 1이 나온다면 서로 다르다는 의미다.
				if( (matrixA[i][j] ^ matrixB[i][j]) == 1) {
					bitNotOperation(i, j);
					ret += 1;
				}
			}
		}
		
		for(int i=0;i<N; i++) {
			for(int j=0; j<M; j++) {
				if( matrixA[i][j] != matrixB[i][j]) {
					return -1;
				}
			}
		}
		return ret;
	}
	
	static void bitNotOperation(int sr, int sc) {
		for(int i=sr; i<sr+3; i++) {
			for(int j=sc; j<sc + 3; j++) {
				matrixA[i][j] = ~matrixA[i][j] & 1; 
			}
		}
	}
	
}