[백준,BOJ 1080] 행렬 (JAVA 구현)

백준 1080 행렬

-내 생각

  알고리즘 초보자로서 그리디 알고리즘에 진입하고 나서부터 무언가 굉장히 헷갈리고 자신감이 사라졌다.. 문제를 이해하는데 많은 시간이 걸리지 않았지만, 어떻게 해결해야 할지 너무 막막해서 곧장 다른 분들의 블로그를 통해 문제를 정확하게 이해할 수 있었다. 똑같은 크기의 2차원 배열 A, B가 일치할 때까지의 변환 연산의 횟수를 구하는 것이 핵심인데 변환 연산은 3X3의 고정된 크기로만 변환이 가능하다. 처음에 다른 블로거 분들의 설명을 봤을 때는 '왜 (0,0)부터 뒤집기 시작하지?' 생각했는데, 생각해보면 3X3으로 고정되어있기 때문에 뒤집은 똑같은 3X3의 공간을 다시 뒤집는 바보 같은 짓(정말 똑같은 공간, 걸치는 공간은 몇 번이든 뒤집어질 수 있다.)을 제외하면 결국에는 각 원소가  뒤집어 질 수 있는 경우가 바로 (0,0) ~ (N-3, M-3)까지 였다.

 

-해법

  3X3의 고정 크기로 변환 연산이 가능하기 때문에 모든 원소를 비교할 필요가 없다. 즉,  (0,0) ~ (N-3,M-3)의 원소들만을 기준으로 3X3의 크기로 비교해가며 변환 연산을 수행한다. 말 그대로 그리디 알고리즘스럽게, A와 B배열의 원소 하나하나를 비교해 가며 다를 때마다 변환 연산을 수행하는데 그 범위가 (N-3, M-3)을 넘어가서는 안된다.

 

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

public class Main {
	static int n,m;
	static int a[][],b[][];
	public static boolean flip(int start_a,int start_b) { // 변환 연산메소드
		
		if(start_a+3>n || start_b+3>m) return false; //전달받은 i와j가 범위를 벗어난다면 false 반환
		
		for(int i=start_a;i<=start_a+2;i++) { // 3x3크기만큼 변환연산을 수행해 준 후 true를 반환			
			for(int j=start_b;j<=start_b+2;j++) {
				a[i][j]= 1-(a[i][j]);					
			}
		}
		return true;
	}
	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());
		
		a = new int[n][m];
		b = new int[n][m];
		
		for(int i =0;i<n;i++) {
			String row = br.readLine();
			for(int j=0;j<m;j++) {				
				a[i][j] =row.charAt(j)-'0';
				
			}
		}
		for(int i =0;i<n;i++) {
			String row = br.readLine();
			for(int j=0;j<m;j++) {				
				b[i][j] =row.charAt(j)-'0';
				
			}
		}
		
		
		int cnt =0;
		// 원소 하나하나를 비교해서 다를 때 마다 flip메소드 호출, 범위를 벗어날 때 까지 같지 않다면 
        // 같아질수 없는 배열들이므로 -1출력
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				
				if(a[i][j]!=b[i][j]) {
					if(flip(i,j)) {
						cnt++;
					}else {
						System.out.println("-1");
						return;
					}
				}
				
			}
		}
		
		System.out.println(cnt);
		br.close();
		
	}
	
}