29. 백준 1080번 행렬(그리디)

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

이 문제는 그리디로 접근해야 한다.
그리디는 현재 상황에서 최선을 고르는 과정을 반복해서 답을 찾아가는 것

근데 나는 개인적으로 저 정의보다 다음과 같이 이해하는게 빨랐다.
그리디는 뒷 일을 생각하지 않는 거다!!

풀이법

이 문제에서도 풀이법은
“처음부터 답안과 비교해 다른 원소를 만나면 그 원소를 바꾼다.” -> 현재 상황의 최선
그리고 문제 조건에 따라 뒤에 따라오는 원소들(3x3배열 만큼)도 바꾼다. -> 이건 어찌되던 지금 신경 안씀

검증

자 이게 진짜 작동하는지 검증해보자!!!
그리디 검증은 최적해를 구하는 임의의 알고리즘을 가정하고, 이 것이 우리 방법보다 좋지 않음을 보이면 된다.

임의의 배열 arr이 있다고 할 때
우리의 풀이로 3번 연산하면 목표 배열을 만들 수 있다고 하자.
(이 세 값을 a1, a2, a3라 하자.)

임의의 알고리즘의 최소 연산 2개라고 가정하고, 연산이 일으키는 위치 b1, b2가 있다고 하자.

이때 주어진 배열이 목표 배열과 다른 가장 처음 위치는 a1이다.
연산을 통해 a1의 위치를 바꿀 수 있는 원소는 a1 자신과, a1보다 왼쪽에 있거나, 위에 있거나, 왼쪽 대각선에 있는 원소일 것이다.
그러나 a1 이전에 있는 원소들은 이미 목표 값과 맞는 원소들이다. 즉 하나의 값을 맞추기 위해 이미 맞는 원소들 바꾸게 되어, 더 연산하게 된다.

코드

package week4;

import java.util.*;
import java.io.*;
public class No1080{
    static int N;
    static int M;
    static char [][] arr1;
    static char [][] arr2;
    public static void change(int a, int b){
        for(int i = 0 ; i < 3 ; i++){
            for(int j = 0 ; j < 3 ; j++){
                if(arr1[a+i][b+j] == '0') arr1[a+i][b+j] = '1';
                else arr1[a+i][b+j] = '0';
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(
                new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr1=new char[N][M];
        arr2=new char[N][M];
        int result = 0;
        for(int i = 0 ; i < N ; i++){
            arr1[i] = bf.readLine().toCharArray();
        }
        for(int i = 0 ; i < N ; i++){
            arr2[i] = bf.readLine().toCharArray();
        }
        for(int i = 0 ; i < N-2 ; i++){
            for(int j = 0 ; j < M-2 ; j++){
                if(arr1[i][j]!= arr2[i][j]){
                    change(i,j);
                    result++;
                }
            }
        }
        if (!Arrays.deepEquals(arr1,arr2)) System.out.println(-1);
        else System.out.println(result);
    }
}