[백준] 1080 : 행렬 (JAVA)

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

1080번: 행렬

Solution

대표적인 그리디 문제다. 너무 복잡하게 생각하느라고 시간을 낭비한 편이다(...) 문제를 풀면서 깨달은 점은

1. 0->1, 1->0 뒤집기 문제에서는 불일치 하는 숫자를 최대한 한번에 많이 뒤집으려고 하는 시도가 무의미하다.. 
   => 2번 뒤집으면 원상복귀한다.
   => 전부 일치하게 만드는 뒤집기가 아닌 이상 부분적으로 불일치가 일어난다. 이후에 처리가 되는지 알 수가 없다.
2. 현재 뒤집는 시도가 이전에 뒤집어 맞춰놓은 배열에 영향을 끼쳐서는 안된다.
   => 3x3 범위의 왼쪽 맨위 지점만을 비교하여 불일치 시 범위 내 배열을 모두 뒤집는다 (범위 내 다른 값은 비교하지 않음)

import java.util.*;
import java.io.*;

class Main
{
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		st=new StringTokenizer(br.readLine()," ");
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] A=new int[N][M];
		int[][] B=new int[N][M];
		
		for(int i=0;i<N;i++) {
			String input = br.readLine();
			for(int j=0;j<M;j++) {
				A[i][j]=input.charAt(j)-'0';
			}
		}
		for(int i=0;i<N;i++) {
			String input = br.readLine();
			for(int j=0;j<M;j++) {
				B[i][j]=input.charAt(j)-'0';
			}
		}
		
		int cnt=0;
		if(N>=3&&M>=3) {
			for(int i=0;i<N-2;i++) {
				for(int j=0;j<M-2;j++) {
					if(A[i][j]!=B[i][j]) {
						for(int x=i;x<i+3;x++) {
							for(int y=j;y<j+3;y++) {
								if(A[x][y]==0) A[x][y]=1;
								else A[x][y]=0;
							}
						}
						cnt++;
					}
				}
			}
		}
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(A[i][j]!=B[i][j]) {
					System.out.println(-1);
					return;
				}
			}
		}
		
		System.out.println(cnt);
		
	}
}