[BOJ/Greedy] 백준 1080 - 행렬 (Java)

1080 - 행렬

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

문제

0과 1로만 이뤄진 행렬 A, B
행렬을 변환하는 연산은 어떤 3x3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것 (0 -> 1, 1 -> 0)

=> 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값?

입력
첫째 줄: 행렬의 크기 N, M (N, M (자연수) <= 50)
둘째 줄부터 N개의 줄: 행렬 A
그 다음줄부터 N개의 줄: 행렬 B
출력: 정답
만약 A를 B로 바꿀 수 X => -1 출력

---

풀이

• 3x3 범위 => `i <= N - 3` / `j <= M - 3`
• 0 <-> 1: `1 - A[x][y]`

int cnt = 0;
for (int i = 0; i <= N - 3; i++) {
    for (int j = 0; j <= M - 3; j++) {
        if (A[i][j] != B[i][j]) {
            for (int x = i; x < i + 3; x++) {
                for (int y = j; y < j + 3; y++) {
                    A[x][y] = 1 - A[x][y];
                }
            }
            cnt++;
        }
    }
}

---

코드

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

// 행렬
public class boj_1080 {
    static int N, M;
    static int[][] A, B;

    public static boolean isSame() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (A[i][j] != B[i][j]) return false;
            }
        }
        return true;
    }

    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());

        A = new int[N][M];
        B = new int[N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                A[i][j] = s.charAt(j) - '0';
            }
        }

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                B[i][j] = s.charAt(j) - '0';
            }
        }

        int cnt = 0;
        for (int i = 0; i <= N - 3; i++) {
            for (int j = 0; j <= M - 3; j++) {
                if (A[i][j] != B[i][j]) {
                    for (int x = i; x < i + 3; x++) {
                        for (int y = j; y < j + 3; y++) {
                            A[x][y] = 1 - A[x][y];
                        }
                    }
                    cnt++;
                }
            }
        }

        System.out.println(isSame() ? cnt : -1);
    }
}