1080 행렬 (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부터 n-2, m-2까지 두개의 행렬에서의 값이 다르면 행렬 변환 연상을 진행하는 그리디 알고리즘을 통해 해결한다.

코드

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

public class Main{

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] graph1 = new int[n][m];
        int[][] graph2 = new int[n][m];


        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                graph1[i][j] = s.charAt(j) - '0';
            }
        }


        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                graph2[i][j] = s.charAt(j) - '0';
            }
        }

        int ans = 0;

        for (int i = 0; i < n-2; i++) {
            for (int j = 0; j < m-2; j++) {
                if (graph1[i][j] != graph2[i][j]) {
                    change(graph1,i,j);
                    ans++;
                }
            }
        }

        System.out.println(check(graph1,graph2) ? ans : -1);


    }

    static void change(int[][] graph, int x, int y) {
        for (int i = x; i < x + 3; i++) {
            for (int j = y; j < y + 3; j++) {
                if (graph[i][j] == 1) {
                    graph[i][j] = 0;
                }else{
                    graph[i][j] = 1;
                }
            }
        }
        return;
    }

    static boolean check(int[][] graph1, int[][] graph2) {
        for (int i = 0; i < graph1.length; i++) {
            for (int j = 0; j < graph1[0].length; j++) {
                if (graph1[i][j] != graph2[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }
}