[백준 / JAVA] 1080번, 행렬 (Greedy)

---

풀이

1. 3 x 3 이 안될 시에는 뒤집을 수 없으므로, 같은지 아닌지만 판단한다는 것을 생각하였고,

2. 3 x 3 이상이 될 시, 3x3 행렬의 좌 상단 1개 만을 비교해서 뒤집어 준다. 

 왜? 그랬냐?

 - 3 x3 행렬 변환이 다른 부분과 겹칠 가능성을 없애기 위해서,

 - 연산 범위를 한정하여 효율을 높이기 위해서,

3. 연산이 끝나고 서로 같지 않으면 return -1 끝! 

 

---

소스 코드

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

public class Main {
    static int n, m, answer;
    static int[][] matA;
    static int[][] matB;

    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());
        matA = new int[n][m];
        matB = new int[n][m];

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < str.length(); j++) {
                matA[i][j] = str.charAt(j) - '0';
            }
        }

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < str.length(); j++) {
                matB[i][j] = str.charAt(j) - '0';
            }
        }

        answer = solve();
        System.out.println(answer);
    }

    static int solve() {
        if (n < 3 || m < 3) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (matA[i][j] != matB[i][j]) return -1;
                }
            }
            return 0;
        }

        int rate = 0;
        for (int i = 0; i <= n - 3; i++) {
            for (int j = 0; j <= m - 3; j++) {
                if (matA[i][j] != matB[i][j]) {
                    flip3x3(i, j);
                    rate++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matA[i][j] != matB[i][j]) return -1;
            }
        }

        return rate;
    }

    static void flip3x3(int x, int y) {
        for (int i = x; i < x + 3; i++) {
            for (int j = y; j < y + 3; j++) {
                matA[i][j] = 1 - matA[i][j];
            }
        }
    }
}