[백준] 행렬 1080 [JAVA]

출처 : www.acmicpc.net/problem/1080

1080번: 행렬

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

풀이 - 사고 과정

Q1. 각 위치마다 중복해서 뒤집을 수도 있고, 순서에 따라 결과값이 달라지지 않을까? 
      - 그럼 모든 순열?? 중복도 가능하고?? 그러면 너무 많은 케이스에다가 무한으로 체크 해야 하는데???
      - matA -> matB 로 바꿀 수 없다는 건 어떻게 증명할 수 있지??

E1. 몇 시간 고민해도 최소 뒤집는 횟수를 구할 방법을 찾아내지 못했다. ㅠㅠㅠ ( 화가 남 ㅠㅠㅠㅠ ) 
E1. 결국, 구글링 ㅠㅠ 

A1. 중복해서 뒤집을 수 있는 건 맞다. 하지만, 아무리 순서를 바꿔서 여러 번 뒤집는다 해도 
     결론적으로, matB 비교할 때는 뒤집었던 순서는 고려할 필요가 없다.

R1. 왜? 
 ex. 

1	0	1	0	1
0	0	1	0	0
0	1	1	0	0
0	0	0	1	1
1	0	1	0	0

1. ( 0 , 0 ) 수정 [빨] -> ( 0, 2 ) 수정 [보] -> ( 0, 1 ) 수정 [ 녹 ]

=> 어차피 순서에 관계없이 matB는 동일한 결과 값을 갖게 된다.
== matA에서도 여러 순서 고려해서 ( 예를 들어 매번 (0,0) 에서 시작한다든지 ) 하면 끝도 안날 뿐더러 의미 없음.  

2. 따라서 최소의 횟수를 구하기 위해서는 mat A 와 mat B를 비교하며 다를 때, 뒤집는게 최선이다.
   ( 0,0 ) -> ( N-1, M-1)로 탐색 하면서  

3. 끝까지 가서 뒤집고 mat A 와 mat B가 다르다면, answer = -1 바꿔주기.

4. 결과론적으로 보면 이러한 로직이 Greedy Algorithm 이라 함.

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다.

예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자.[1] 이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다.

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 위의 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다.

그리디 알고리즘을 한마디로 설명한다면 그 유명한 마시멜로 실험에 비유할 수 있겠다. 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는 것이다. 하지만 이 방법을 사용하는 것은 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못한다.

코드

package 알고리즘스터디문제;

import java.util.Scanner;

/*
 * 왜, 다시 ( 0,0 ) 에서 시작 안해도 될까?
 * 
 * ex. (0,0) 수정 -> ( 0,2 ) 수정 -> ( 0,1 ) 수정 
 */

public class 행렬_1080 {
	static int[][] matA;
	static int[][] matB;
	static int N , M;
	static int answer = 0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		matA = new int [N][M];
		matB = new int [N][M];
		
		
		// matA input
		for ( int i=0; i<N; i++) {
			String str = sc.next();
			for ( int j=0; j<M; j++) {
				matA[i][j] = str.charAt(j);
			}
		}
		
		// matB input
		for ( int i=0; i<N; i++) {
			String str = sc.next();
			for ( int j=0; j<M; j++) {
				matB[i][j] = str.charAt(j);
			}
		}
		
		// 뭐 바꿀 수 있는게 없잖아.
		if ( N < 3 || M < 3) {
			if ( IsSame(matA,matB) ) {
				answer = 0;
			}
			else {
				answer = -1;
			}
		}
		// 바꿔보자
		else {
			Solution();
		}
		
		if( !IsSame(matA, matB)) {
			answer = -1;
		}
		
		System.out.println(answer);
	}

	private static void Solution() {
		// TODO Auto-generated method stub
		// 3*3 만 바꿀 수 있으니, ( N-2, M-2 ) 까지밖에 못감
		for( int i=0; i<N-2 ; i++) {
			for ( int j=0; j<M-2 ;j ++) {
				if ( matA[i][j] != matB[i][j]) {
					filp(i,j);
					answer ++;
				}
			}
		}
	}

	private static void filp(int cr, int cn) {
		// TODO Auto-generated method stub
		
		for ( int i=cr; i< cr+3; i++) {
			for ( int j=cn; j<cn+3; j++) {
				matA[i][j] = matA[i][j] ^ 1 ; // 뒤집기
			}
		}
		
	}

	private static boolean IsSame(int[][] matA2, int[][] matB2) {
		// TODO Auto-generated method stub
		for ( int i=0; i<N; i++) {
			for ( int j=0; j<M;j ++){
				if ( matA2[i][j] != matB2[i][j] ) return false; 
			}
		}
		
		return true;
	}
}