BOJ1080 행렬 java

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

풀이방법

첫 번째 점(0,0)을 살펴보면 아이디어를 얻을 수 있다.

(0,0)이 뒤집힐 수 있는 경우의 수는 단 한 개밖에 없다.

바로 (0,0) 에서 3x3을 뒤집었을 때

첫 번째 점(0,0)을 뒤집어야 한다면 뒤집는다.

그 다음에는 그 옆에 있는 점(0,1 혹은 1,0)이 뒤집힐 수 있는 경우의 수는 단 한 개밖에 없다.

첫 번째 점(0,0)을 시작으로 다음 점의 뒤집기 여부를 알 수 있다.

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

class Main {
    static char[][] matrixA;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int M = Integer.valueOf(st.nextToken());
        matrixA = new char[N][M];
        char[][] matrixB = new char[N][M];
        for (int i = 0; i < N; i++) {
            String row = br.readLine();
            matrixA[i] = row.toCharArray();
        }

        for (int i = 0; i < N; i++) {
            String row = br.readLine();
            matrixB[i] = row.toCharArray();
        }

        int result = 0;
        for (int i = 0; i <= N - 3; i++) {
            for (int j = 0; j <= M - 3; j++) {
                if (matrixA[i][j] != matrixB[i][j]) {
                    result++;
                    change(i, j);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrixA[i][j] != matrixB[i][j]) {
                    System.out.println(-1);
                    return;
                }
            }
        }
        System.out.println(result);
    }

    private static void print(int n, int m, char[][] matrixB) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(matrixB[i][j]);
            }
            System.out.println();
        }
    }

    private static void change(int x, int y) {
        for (int i = x; i < x + 3; i++) {
            for (int j = y; j < y + 3; j++) {
                matrixA[i][j] = matrixA[i][j] == '1' ? '0' : '1';
            }
        }
    }
}