[BOJ] 1080번_행렬_그리디 (C++)

[문제]

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

0과 1로 이루어진 A행렬과 B행렬을 입력받아 A행렬을 B행렬로 바꾸는데 필요한 최소 연산 횟수를 구하는 문제이다.

• 연산은 행렬의 3x3크기의 부분을 전부 뒤집는 것이다.

[사용 알고리즘]

그리디

[풀이 핵심]

• 입력이 띄어쓰기가 없으므로 cin이 아닌 scanf_s("%1d", OOO)을 이용해서 입력받아야 한다.
  (백준 사이트에선 scanf_s가 아닌 scanf를 사용해야 한다.)
• A행렬을 돌면서 B행렬과 다른 부분을 찾았을 때 다른 부분을 기점으로 3x3크기의 부분을 전부 뒤집고, 연산횟수 변수인 result를 증가시켜준다.
  (3x3크기의 부분에서 연산이 진행되므로 원소가 다른 부분을 기점으로 행 또는 열이 2칸이상 남아있지 않으면 연산할 수 없기 때문에 N-2, M-2까지 탐색을 진행한다.)
• 모든 연산이 끝난 후에 A행렬과 B행렬을 비교해서 같으면 result, 다르면 -1을 출력해준다.

[코드]

//boj1080번_행렬_그리디 알고리즘

#include<iostream>

using namespace std;

int arr1[51][51];
int arr2[51][51];

int main() {
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf_s("%1d", &arr1[i][j]);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf_s("%1d", &arr2[i][j]);
		}
	}

	int result = 0;

	for (int i = 0; i < N - 2; i++) {
		for (int j = 0; j < M - 2; j++) {
			if (arr1[i][j] != arr2[i][j]) {
				result++;
				for (int x = i; x < i + 3; x++) {
					for (int y = j; y < j + 3; y++) {
						if (arr1[x][y] == 0) {
							arr1[x][y] = 1;
						}
						else {
							arr1[x][y] = 0;
						}
					}
				}
			}
		}
	}
	
	bool check = true;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr1[i][j] != arr2[i][j]) {
				check = false;
			}
		}
	}

	if (check) {
		cout << result;
	}
	else {
		cout << -1;
	}
}
}