Baekjoon_1080_행렬

문제 설명

1080번: 행렬

• 0과 1로만 이루어진 행렬 A와 B
• 한 번의 연산 : 3*3크기의 부분행렬 Toggle( 0 <-> 1)

=> 행렬 A를 B로 바꾸는 연산의 최솟값 출력(바꿀 수 없다면 -1출력)

 

 

문제 풀이

A를 B의 행렬 모양으로 바꾸는 방법을 찾아야 하므로, 두 행렬의 다른 부분을 우선 찾아야 한다.

 

A행렬과 B행렬을 비교하여 서로 다른 부분을 true로 표시하는 2차원 boolean배열(check)을 만들었다.

 

그리고 check배열의 (N-3) * (M-3)범위를 확인하면서 true인 부분이 발견되면 그 부분을 기준으로 3 * 3 범위의 부분행렬을 뒤집고 뒤집은 횟수를 1 늘렸다.

 

위의 과정을 거치면 (N-3) * (M-3)부분은 전부 false형태가 된다.

 

하지만 3*3부분행렬이 직접적으로 건들지 않는 N-2 ~ N-1 과 M-2 ~ M-1부분에 true가 존재한다면 A행렬과 B행렬은 동일하지 않다는 의미가 된다.

 

따라서 (N-3) * (M-3)를 조정하던 중 N-3을 검사할때는 N-2와 N-1을, M-3을 검사할 때는 M-2와 M-1을 확인하여 true가 있는지 확인하고, 존재한다면 더 검사할 의미가 없으므로 -1을 나타내도록 했다.

 

그리고 확인을 못하는 마지막의 4 구역(N-2,M-2),(N-1,M-2),(N-2,M-1),(N-1,M-1)을 최종적으로 확인하여 결과를 출력했다.

 

또한 문제에서는 N과 M의 최댓값만 주어졌을 뿐, 최솟값은 주어지지 않았다. 따라서 N과 M이 2이하일 경우 3*3 부분행렬로 뒤집을 수 없으므로 A와 B행렬 초기값을 비교하여 연산 결과를 나타내었다.

 

문제 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _1080_행렬 {
	static int N, M, min = Integer.MAX_VALUE;
	static char[][] A, B;
	static boolean[][] check;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		A = new char[N][];
		B = new char[N][];
		for (int i = 0; i < N; ++i) {
			A[i] = in.readLine().toCharArray();
		}
		for (int i = 0; i < N; ++i) {
			B[i] = in.readLine().toCharArray();
		}
		check = new boolean[N][M];

		for (int i = 0; i < N; ++i) { // 두 배열 비교. 다르면 True
			for (int j = 0; j < M; ++j) {
				check[i][j] = A[i][j] != B[i][j];
			}
		}
		int count = 0;
		if (N < 3 || M < 3) {
			out: for (int i = 0; i < N; ++i) { // 두 배열 비교. 다르면 3*3 뒤집기
				for (int j = 0; j < M; ++j) {
					if (check[i][j]) {
						count = -1;
						break out;
					}

				}
			}
			System.out.println(count);
		} else {

			out: for (int i = 0; i <= N - 3; ++i) {
				for (int j = 0; j <= M - 3; ++j) {
					if (check[i][j]) {
						++count;
						change(i, j);
					}

					if (i == N - 3) { // 아래쪽 남은 끝 2칸 확인
						if (check[i + 1][j] || check[i + 2][j]) {
							count = -1;
							break out;
						}
					}
					if (j == M - 3) { // 오른쪽 남은 끝 2칸 확인
						if (check[i][j + 1] || check[i][j + 2]) {
							count = -1;
							break out;
						}
					}
				}
			}

			if (check[N - 2][M - 2] || check[N - 1][M - 2] || check[N - 2][M - 1] || check[N - 1][M - 1])	//맨 마지막 4칸 확인
				count = -1;

			System.out.println(count);
		}
	}

	static void change(int i, int j) {	//3*3 뒤집기
		for (int r = i; r < i + 3; ++r) {
			for (int c = j; c < j + 3; ++c) {
				check[r][c] = !check[r][c];
			}
		}
	}

}