백준 1080번 : 행렬 java

이 문제는 그리디 알고리즘을 이용하여 푸는 문제입니다.

이 문제를 풀기 위해서는 N, M을 입력받은 후 맨 처음 칸부터 행렬 A와 행렬 B가 같은지 확인하여 다르다면 그 칸을 시작으로  3x3만큼의 크기만큼을 바꾸어주어야 합니다.

이 위의 그림은 예제 1번을 나타낸 그림입니다.

이 그림에서 A의 1행 1열은 B의 숫자와 다릅니다. 따라서 이 칸을 기준으로 3x3 크기의 칸의 수를 바꾸겠습니다.

뒤집을 영역의 크기는 아래의 그림과 같습니다.

이를 뒤집으면 아래의 그림과 같이 됩니다.

그리고 A의 1행 1열을 보면 B 행렬과 다르기 때문에 위에 같이 뒤집어 줍니다.

뒤집을 영역은 아래와 같습니다.

이제 아래의 그림과 같이 A행렬과 B행렬이 같아졌습니다.

위와 같이 처음부터 A행렬과 B행렬을 비교해가면 이 문제를 해결할 수 있습니다.

---

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

public class Main {
    static int N, M, cnt = 0;
    static int[][] map;
    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());

        map = new int[N][M];
        int[][] target = new int[N][M];

        for(int i = 0; i<N; i++){
            String[] input = br.readLine().split("");

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

            for(int j = 0; j<M; j++)
                target[i][j] = Integer.parseInt(input[j]);
        }

        for(int i = 0; i<N-2; i++){
            for(int j = 0; j<M-2; j++){
                if(map[i][j] != target[i][j]){
                    change(i, j);
                }
            }
        }

        boolean okay = true;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++)
                if(map[i][j] != target[i][j]) {
                    okay = false;
                    break;
                }
            if(!okay)
                break;
        }

        if(okay)
            System.out.println(cnt);
        else
            System.out.println(-1);
    }

    static void change(int row, int col){
        int[] dR = {0, 1, 2, 0, 1, 2, 0, 1, 2};
        int[] dC = {0, 0, 0, 1, 1, 1, 2, 2, 2};

        cnt++;

        for(int i = 0; i<9; i++){
            int dr = row + dR[i];
            int dc = col + dC[i];

            if(dr>=N||dc>=M)
                return;

            boolean isZero = map[dr][dc] == 0;
            if(isZero)
                map[dr][dc] = 1;
            else
                map[dr][dc] = 0;
        }
    }
}

정해진 칸을 넘으면 안 되기 때문에 열은 N-2, 행은 M-2칸까지 순회해줍니다.