백준 1080번 행렬(JAVA,그리디)

<풀이방식>

A 배열에서 B 배열로 바뀌는 알고리즘이 있을것이라 생각해서 고민했는데 도저히 생각이 안났다.

결국 친구가 알려주기를 3*3 배열 크기만큼 검사 가능한 지점마다 모두 체크를해야한다고 했다.

즉, 예제의 경우 (0,0) , (0,1) 지점이 가능한 지점이며 이 지점마다 A,B배열의 값이 다르다면 뒤집어야한다. 이유는 이 지점은 다시는 돌아오지 않기 때문에 지금 다르면 바로 뒤집어야하는 것이다.

이렇게 뒤집으며 지나갔을때 결과가 같다면 뒤집으면서 센 카운트가 정답이고 다르다면 그냥 -1을 출력하면된다.

---

생각보다 단순한 알고리즘으로 풀이 가능한데 그리디적인 사고를 못한것이 아쉽다.

그리고 배열 값을 1에서 0으로 , 0에서 1로 바꾸는 경우 단순하게 값을 바꿨는데 계속 오류가났고 비트 뒤집기를 쓰니까 해결됐다. 왜인진 모름 ..

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

public class Main {
	public static int row;
	public static int col;
	public static int[][] A;
	public static int[][] B;
	public static int cnt;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		row = sc.nextInt();
		col = sc.nextInt();
		A = new int [row][col];
		B = new int [row][col];

		//기본 map 세팅
		for(int i = 0 ; i <row; i ++) {
			String str = sc.next();
			for(int j = 0 ; j < col ; j++) 
				A[i][j] = Integer.parseInt(str.substring(j,j+1));
		}

		//바꾸고 싶은 map 세팅
		for(int i = 0 ; i <row; i ++) {
			String str = sc.next();
			for(int j = 0 ; j < col ; j++) 
				B[i][j] = Integer.parseInt(str.substring(j,j+1));
		}

		cnt = 0;
		//탐색 시작(배열 범위 넘어가지않게 row-2 , col-2 까지만 돌림
		for(int i = 0 ; i < row-2; i++) {
			for(int j = 0 ; j < col-2; j++) {
				// i,j 가 다르다면 뒤집는다(이 지점은 다시뒤집을수 없는 지점이므로 무조건 뒤집음)
				if(A[i][j] != B[i][j]) {
					change(i,j);
					cnt++;
				}
			}
		}

		//A,B배열이 같은지 확인
		int flag = 0;
		for(int i = 0 ; i < row ; i++) {
			for(int j = 0 ; j < col ; j++) {
				if(A[i][j] == B[i][j])
					flag ++;
			}
		}

		if(flag == row*col)
			System.out.println(cnt);
		else 
			System.out.println(-1);

	}

	
	//i,j 기준으로 3*3 크기만큼 비트 뒤집기
	public static void change(int x , int y) {
		for(int i = x ; i <x+3 ; i++) {
			for(int j = y; j<y+3 ; j++) {
				A[i][j] = A[i][j] ^ 1 ;
			}
		}
	}


}