[백준 1080번] 행렬 (java)

1080번: 행렬

 

A[r][c]에 대하여 A[r][c]!=B[r][c] 이면, (r, c)를 시작으로하는 3*3 행렬만큼 0은 1로, 1은 0으로 뒤집는다.

위 과정을 r = 0, c = 0 부터 마지막까지 반복한다.

 

이렇게 하는 이유는 만약에 A[0][0]!=B[0][0] 라면 B[0][0]와 같게 하기 위해 A[0][0]를 뒤집어야 한다.

그런데 A[0][0]를 뒤집기 위해서는 결국 (0,0)을 맨 왼쪽위로 하는 3*3 행렬만큼을 뒤집어야 한다.

 

 

A[0][1]도 마찬가지이다. A[0][1] != B[0][1] 라면 B[0][1]와 같게 하기 위해서 A[0][1]를 뒤집어야 하는데,

이 때 (0,1)을 포함하는 3*3 행렬만큼 뒤집어주면 된다.

그런데 (0,0)은 이미 이 직전에 한 번 뒤집어서 변경해주었다. 뒤집은 자리를 한 번 더 뒤집어주면 불필요한 연산을 한 번 더 해주는 것이기 때문에 연산의 최소횟수를 구할 수 없게 된다.

그러므로 (0,0)을 포함시키지 않도록 (0,1)을 맨왼쪽위로 하는 3*3 행렬만큼을 뒤집어야 한다.

 

이런식으로 r = 0, c = 0 부터 시작해서 A[r][c]가 B[r][c]와 다르면 해당 위치를 맨 왼쪽위로 하는 3*3 행렬만큼의 요소를 뒤집어준다.

여기서 핵심은 3*3 행렬이 계속 이동하면서, 이미 뒤집은 요소(회색부분)는 다시는 뒤집지 않는다.

그렇기 때문에 연산을 최소로 하면서 행렬 A를 행렬 B와 일치시키도록 바꿔나갈 수 있다.

 

 

만약 반복이 끝났는데도 행렬 A와 행렬 B가 일치하지 않는다면 -1을 출력하고,

일치한다면 3*3만큼 뒤집은 횟수를 출력한다.

 

 

소스코드 :

	import java.io.*;
	import java.util.*;
	public class n01080 {
	static int N, M;
	static int[][] A, B;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] sarr = br.readLine().split(" ");
	N = Integer.parseInt(sarr[0]);
	M = Integer.parseInt(sarr[1]);
	A = new int[N][M];
	B = new int[N][M];
	for (int i = 0; i < N; i++) {
	String str = br.readLine();
	for (int j = 0; j < M; j++) {
	A[i][j] = str.charAt(j) - '0';
	}
	}
	for (int i = 0; i < N; i++) {
	String str = br.readLine();
	for (int j = 0; j < M; j++) {
	B[i][j] = str.charAt(j) - '0';
	}
	}
	int cnt = 0;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if (A[i][j] != B[i][j] && i + 2 < N && j + 2 < M) {
	for (int r = i; r < i + 3; r++) {
	for (int c = j; c < j + 3; c++) {
	A[r][c] = A[r][c] == 0 ? 1 : 0;
	}
	}
	cnt++;
	}
	}
	}
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if (A[i][j] != B[i][j]) {
	bw.write(-1 + "\n");
	bw.flush();
	return;
	}
	}
	}
	bw.write(cnt + "\n");
	bw.flush();
	}
	static class Pos {
	int r, c;
	Pos(int r, int c) {
	this.r = r;
	this.c = c;
	}
	}
	}

view raw 1080.java hosted with ❤ by GitHub