[백준] 1080번: 행렬(그리디)

https://www.acmicpc.net/problem/1080

1080번: 행렬

코드

import java.util.Scanner;

public class Main {
	static int N;			// 행
	static int M;			// 열
	static int[][] aArr;	// 행렬 A
	static int[][] bArr;	// 행렬 B
	static int count = 0;	// 연산의 횟수

	// 3*3 부분 행렬의 모든 원소 뒤집기(0->1, 1->0)
	public static boolean reverseArr(int row, int col){

		// 전달받은 인덱스 i, j가 변환할 범위를 벗어날때
		if(row+3 > N || col+3 > M)
			return false;

		for(int i=row; i<row+3; i++) {
			for(int j=col; j<col+3; j++) {
				if(aArr[i][j] == 0) 
					aArr[i][j] = 1;
				else
					aArr[i][j] = 0;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		M = scan.nextInt();
		aArr = new int[N][M];
		bArr = new int[N][M];

		for(int i=0; i<N; i++) {
			String str = scan.next();
			for(int j=0; j<M; j++) 
				aArr[i][j] = str.charAt(j) - '0';
		}
		for(int i=0; i<N; i++) {
			String str = scan.next();
			for(int j=0; j<M; j++) 
				bArr[i][j] = str.charAt(j) - '0';
		}

		// (0,0)부터 원소를 일일이 비교해가며 다를경우 reverseArr 메서드를 통해 원소 뒤집음.
		// 3*3 크기의 행렬이 고정이므로, 범위를 벗어날 떄까지 같지않을경우, -1 출력
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(aArr[i][j] != bArr[i][j]) {
					if(reverseArr(i, j)) {
						count ++;
					} else {
						System.out.println("-1");
						return;
					}
				}
			}
		}

		System.out.println(count);
		scan.close();
	}

}

 

풀이

변수들을 다른 메소드에서 사용할 수 있도록 클래스 변수(static)로 선언했다.

2차원 행렬 A, B의 각각의 원소들을 오른쪽 아래로 값을 비교해가면서 값이 다를때, 부분 행렬(3*3)의 모든 원소들을 뒤집어 주면 된다.

부분 배열의 크기가 3*3이므로, i와 j는 N-3, M-3 까지만 비교해주면 된다.

만약 N = 3 , M = 5인 3 * 5 인 행렬이 있을때,

 

A 행렬은

0 0 1 0 1

0 0 1 1 0

0 0 1 1 1 이고,

 

B 행렬은

0 0 1 0 0

0 0 1 1 0

0 0 1 0 0 일때,

 

j(열)의 값은 각 행마다 2까지만 비교하면 두 행렬이 원소를 뒤집었을때 같은지 다른지 알 수 있다.

왜냐하면 3*3인 부분 배열 이므로 j=4 일때 두 행렬의 원소가 다르지만, 3*3인 부분 행렬을 뒤집을 수가 없다.

 

따라서 부분 행렬의 모든 원소를 뒤집는 메소드 reverseArr()를 통해 원소를 뒤집는데, 이 때

i, j의 값이 범위를 벗어났을때는 false로 리턴하고, 범위 안일경우 행렬의 3*3 부분 행렬을 뒤집어준다.

 

	// 3*3 부분 행렬의 모든 원소 뒤집기(0->1, 1->0)
	public static boolean reverseArr(int row, int col){
		
		// 전달받은 인덱스 i, j가 변환할 범위를 벗어날때
		if(row+3 > N || col+3 > M)
			return false;
		
		for(int i=row; i<row+3; i++) {
			for(int j=col; j<col+3; j++) {
				if(aArr[i][j] == 0) 
					aArr[i][j] = 1;
				else
					aArr[i][j] = 0;
			}
		}
		return true;
	}

 

 

 

main 메소드에서 두 행렬 A, B의 모든 원소들을 탐색하면서 값이 다를경우 부분 행렬의 원소를 뒤집고,

만약 원소를 뒤집을때 인덱스의 범위에서 벗어났을때는 -1을 출력한다.

 

		// (0,0)부터 원소를 일일이 비교해가며 다를경우 reverseArr 메서드를 통해 원소 뒤집음.
		// 3*3 크기의 행렬이 고정이므로, 범위를 벗어날 떄까지 같지않을경우, -1 출력
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(aArr[i][j] != bArr[i][j]) {
					if(reverseArr(i, j)) {
						count ++;
					} else {
						System.out.println("-1");
						return;
					}
				}
			}
		}