백준 1080번: 행렬

문제 설명

• https://www.acmicpc.net/problem/1080
• 행렬 A를 뒤집어 행렬 B를 만들어야 합니다.
  • 뒤집기는 3x3에 대해 전체 값을 뒤집습니다.
  • 3x3으로 뒤집을 수 없는 경우 뒤집지 않습니다.

접근법

• 같이 뒤집히는 값에 대해서는 고려하지 않습니다.
  • 자신의 차례에 왔을 때 자신만 완벽하게 뒤집을 수 있으면 됩니다.
• (0,0)부터 (N,M)으로 가면서 자신의 값을 뒤집어야 한다면 해당 좌표(i,j)를 가장 왼쪽 상단으로 하는 3x3을 뒤집습니다.
  • 좌상단부터 탐색을 진행하고, 자신을 죄상단으로 설정하기 때문에 이번에 뒤집으면 더 이상 뒤집히지 않습니다.
  • 여기서 뒤집은 결과로 밑에 값이 흐트러지더라도 해당 좌표에 도달했을 때 다시 뒤집으면 됩니다.

pseudocode

func(){
	for(i는 0~N){
    	for(j는 0~M){
        	if(A행렬의 (i,j)값과 B행렬의 (i,j)값이 다르면){
            	if((i,j)를 좌상단으로 3x3이 존재하지 않으면) return -1; // flip 메서드 사용
                뒤집은 횟수 한번 추가 // flip이 유효성 검사를 하면서 실제로 뒤집는 작업도 함
            }
            if(A의 모든 값과 B의 모든 값이 동일하다면) return 뒤집은 횟수 // CheckAllTrue 메서드 활용
        }
    }
}

flip(int r, int c){
	아래의 값이 배열이 범위를 벗어나면 return false
	(r,c),(r,c+1),(r+c,2)
    (r+1,c),(r+1,c+1),(r+1,c+2)
    (r+2,c),(r+2,c+1),(r+2,c+2)의 값을 모두 반대로 뒤집고 return true
}

CheckAllTrue(){
	배열의 모든 값을 순회하면서 false가 발견되면 return false;
    false가 하나도 없다면 return true;
}

정답

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

public class Main {
	static int N,M;
	public static void main(String[] args) throws NumberFormatException, 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());
		int[][] NormalBoard = new int[N][M];
		for (int i = 0; i < N; i++) {			
			String s = br.readLine();
			for (int j = 0; j < M; j++) {
				NormalBoard[i][j] = Integer.parseInt(Character.toString(s.charAt(j)));
			}
		}
		
		int[][] TargetBoard = new int[N][M];
		for (int i = 0; i < N; i++) {			
			String s = br.readLine();
			for (int j = 0; j < M; j++) {
				TargetBoard[i][j] = Integer.parseInt(Character.toString(s.charAt(j)));
			}
		}
		
		// A의 (i,j)값과 B의 (i,j)값이 같다면 true, 다르다면 false
		boolean[][] AnswerBoard = new boolean[N][M];
		for (int i = 0; i < N; i++) {			
			for (int j = 0; j < M; j++) {				
				if(NormalBoard[i][j] == TargetBoard[i][j]) {
					AnswerBoard[i][j] = true;
				}else {
					AnswerBoard[i][j] = false;					
				}
			}
		}
		
		
		System.out.println(func(AnswerBoard));
		

	}
	public static boolean flip(int r , int c,boolean[][] board) {
		if(r+2<N && c+2 < M) {
			for (int i = r; i <= r+2; i++) {
				for (int j = c; j <= c+2; j++) {
					board[i][j] = !board[i][j];
				}
			}
			return true;
		}
		return false;
	}
	
	public static boolean CheckAllTrue(boolean[][] AnswerBoard) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(!AnswerBoard[i][j]) return false;
			}
		}
		return true;
		
	}
	
	public static int func(boolean[][] AnswerBoard) {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(!AnswerBoard[i][j]) {
					if(!flip(i,j,AnswerBoard)) return -1;
					cnt++;
				}
				if(CheckAllTrue(AnswerBoard)) return cnt;
			}
		}
		return cnt;
		
	}
	
}