[백준] Greedy: 행렬

문제

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

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

입력

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

출력

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

 

문제 접근

처음에는 행렬은 순환하면서 3x3안에 원소가 다른 경우가 있으면 바꿔야 한다고 생각했다.

만약에 바꿀 원소가 없으면  다음으로 넘어가야하는데...? 어떻게 넘어가지..? 라고 생각하던 중.

다른 사람의 풀이를 보니 Greedy 스럽지 않은 판단이었다.

 

Greedy는 현재!를 기준으로 만 판단하면 된다.

현재? 가 일치하지 않으면 어쨌든 바꿔야 한다. 바꾸는 범위는 3x3이다.

 

즉 Greedy 스럽게 (0, 0) -> (N-3, M-3)을 돌면서 값이 일치하는지 아닌지 만 확인하면 된다.

(i,j) 값이 A행렬과 B행렬이 다르다면? 현재 기준으로 (i,j) ~ (i+2, j+2) 원소를 뒤집으면 된다.

 

만약 뒤집었다고 생각하고 다음 원소(i+1, j)로 넘어간다고 해보자.

이미 한 번 뒤집은 원소일 수도 ? 아닐 수도? 있다.

이 값이 A, B행렬이 일치하는지 판단하자. 일치하면 넘어가면되고, 아니면 또 바꿔주면 된다.

 

이 행위를 끝까지 반복하면 A와 B가 일치할 수도 있고 아닐 수도 있다.

 

일치할 경우 현재 바꿔 준 횟수를 반환하면 된다.

 

물론 이 값은 최적의 값은 아닐 수 도 있다. 하지만 나름 합리적인 해를 찾는 방법이다.

 

Greedy의 의미를 재 확인할 수 있는 문제였다.

 

풀이 코드

package baekjun;

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

public class _1080 {

    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[][] A = new int[N][M];
        int[][] B = new int[N][M];

        makeMatrix(br, N, A);
        makeMatrix(br, N, B);

        int answer = 0;
        if (N >= 3 && M >= 3 ){

            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 k=i; k<i+3; k++){
                            for (int l=j; l<j+3; l++){
                                A[k][l] = (A[k][l] == 0) ? 1 : 0;
                            }
                        }
                        answer++;
                    }
                }
            }

        }

        int code = isEqual(N, M, A, B);

        if (code == 0){
            System.out.println(answer);
        }else System.out.println(-1);


    }

    private static int isEqual(int N, int M, int[][] A, int[][] B) {
        int code = 0;
        for (int i = 0; i< N; i++){
            for (int j = 0; j< M; j++){
                if (A[i][j] != B[i][j]){
                    code = -1;
                    break;
                }
            }
            if (code == -1){
                break;
            }
        }
        return code;
    }

    private static void makeMatrix(BufferedReader br, int N, int[][] A) throws IOException {
        for (int i = 0; i< N; i++){
            String[] numArr = br.readLine().split("");
            for (int j=0; j< numArr.length; j++){
                A[i][j] = Integer.parseInt(numArr[j]);
            }
        }
    }


}