문제

풀면서 어려웠던 점

문제 자체의 이해는 어렵지 않았으나, 이렇게 푸는 것이 왜 정답이 되는가? 에 대한 의문을 지우는 데 오래 걸렸다.

Greedy 알고리즘이 다 그런 것 같다. 이게 왜 정답이지? 싶은게 많다.

정답에 대한 논리적 정당성을 확인하는 과정을 더 거쳐야한다고 생각한다.

0,0 ~ N-3, M-3 까지 탐색해서 다르면 바꾼다?
--> OK, 3*3 배열을 스위칭하는 것이니까 N-3, M-3까지 탐색하는게 맞지.

그렇게만 하면 정답이다. --> ? 왜?

이런 느낌? 분명히 반례가 있을 것 같은데, 찾지는 못했다. 그리디 알고리즘의 유형을 익혀야겠다.

작성한 코드

package Greedy_Algorithm;

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

public class BOJ_1080_행렬 {
	
	static int N, M;
	static int arr[][];
	static int after[][];

	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());
		
		
		arr  = new int[N][M];
		after  = new int[N][M];
		
		for(int i=0; i<N; i++) {
			String temp = br.readLine();
			for(int j=0; j<M; j++) {
				arr[i][j] = temp.charAt(j)-'0';
			}
		}
		
		for(int i=0; i<N; i++) {
			String temp = br.readLine();
			for(int j=0; j<M; j++) {
				after[i][j] = temp.charAt(j)-'0';
			}
		}
		
		if(N<3 || M<3) {
			if(bigyo()) {
				System.out.println(0);
				return;
			}
			System.out.println(-1);
			return;
		}
		
//		System.out.println("arr배열입니다.");
//		for(int i=0; i<N; i++) {
//			for(int j=0; j<M; j++) {
//				System.out.print(arr[i][j]+" ");
//			}System.out.println();
//		}
//		
//		System.out.println("after배열입니다.");
//		for(int i=0; i<N; i++) {
//			for(int j=0; j<M; j++) {
//				System.out.print(after[i][j]+" ");
//			}System.out.println();
//		}
		
		int cnt =0;
		
		for(int i=0; i<=N-3; i++) {
			for(int j=0; j<=M-3; j++) {
				if(arr[i][j]!=after[i][j]) {
					transform(i,j);
					cnt++;
				}
				
				if(bigyo()) {
					System.out.println(cnt);
					return;
				}
			}
		}
		System.out.println(-1);
		return;
		
		
	}
	private static boolean bigyo() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(arr[i][j] != after[i][j])
					return false;
			}
		}
		return true;
	}
	private static void transform (int a, int b) {
		for(int i=a; i<a+3; i++) {
			for(int j=b; j<b+3; j++) {
				if(arr[i][j] ==0) arr[i][j] = 1;
				else arr[i][j] = 0;
			}
		}
	}

}