백준 1080 행렬

백준 행렬 1080 바로가기

문제 설명

0과 1로만 이루어진 같은 크기의 행렬 A, B가 주어진다

A 행렬의 원소를 바꿔서 B로 바꾸려 할 때의 최소 횟수를 구하여라

행렬의 원소를 바꾸는 방법은 3x3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다.

접근 방식

행렬을 전체 탐색 하면서, 해당 위치에서의 A와 B가 다르면 뒤집기를 시도하는거다.

해당 위치를 3x3의 왼쪽 윗 칸이라고 보고 뒤집기를 시도 하면서 횟수를 세어준다.

코드

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

public class Main {
    static int[][] A;
    static int[][] B;
    static int count;

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

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

        for (int i = 0; i < N; i++) {
            String[] x = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                A[i][j] = Integer.parseInt(x[j]);
            }
        }

        for (int i = 0; i < N; i++) {
            String[] x = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                B[i][j] = Integer.parseInt(x[j]);
            }
        }

        if (N < 3 || M < 3) {
            if (isSameMatrix(A, B)) count = 0;
            else count = -1;
        } else {
            for (int i = 0; i < N - 2; i++) {
                for (int j = 0; j < M - 2; j++) {
                    if (A[i][j] != B[i][j]) {
                        myFlip(i, j);
                        count++;
                    }
                }
            }

            if (!isSameMatrix(A, B)) {
                count = -1;
            }

        }
        System.out.println(count);
    }

    private static boolean isSameMatrix(int[][] a, int[][] b) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                if (a[i][j] != b[i][j]) return false;
            }
        }
        return true;
    }

    private static void myFlip(int x, int y) {
        for (int i = x; i <= x + 2; i++) {
            for (int j = y; j <= y + 2; j++) {
                A[i][j] = (A[i][j] == 0 ? 1 : 0);
            }
        }
    }

}

Disscussion

꽤 어려운 문제였다.

그리고 이 방식이 그리디한 풀이라는것에 또 놀랐다..