Problem 1080

행렬

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

문제 링크

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

예제 입력 1

3 4
0000
0010
0000
1001
1011
1001

예제 출력 1

solve

0, 1로만 이루어진 행렬을 같게 만들어야 하는 문제이다. 이 때, 연산은 3x3 행렬을 뒤집는 연산만 사용이 가능하다.
두 행렬을 a, b로 입력을 받는다.
이 때, 만약 a[0][0] 과 b[0][0]이 다르다면 (0, 0)을 같게 만드는 방법은 (0, 0)부터 (2, 2)까지 모든 행렬을 뒤집는 연산을 한 번 수행하는 방법 뿐이다.
- (두 번 수행하게 된다면 다시 연산 이전의 상태로 돌아올 것이고 세 번 수행한다면 한 번 수행한 결과와 같으니 최솟값이 성립하지 않는다.)
따라서, 이 과정을 n - 2, m - 2까지 반복한 결과가 서로 같다면 a를 b로 바꿀 수 있다는 것이고, 연산을 수행할 때마다 카운트한 결과가 정답이 된다.
결과가 서로 다르다면 a를 b로 바꿀 수 없다는 뜻이므로 -1을 출력한다.

코드 설명

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>

using namespace std;
int a[50][50];
int b[50][50];

void reverse33(int x, int y) // 3x3을 뒤집는 함수 0 -> 1, 1 -> 0
{
	for (int i = x; i < x + 3; i++)
	{
		for (int j = y; j < y + 3; j++)
		{
			a[i][j] = 1 - a[i][j]; // a[i][j]가 0이면 1로, 1이면 0으로 바꿈
		}
	}
}

int main(void)
{
	int n, m; // 행렬의 크기
	cin >> n >> m;

	string str;

	for (int i = 0; i < n; i++) // a, b 행렬 입력
	{
		cin >> str;
		for (int j = 0; j < str.length(); j++)
			a[i][j] = str[j] - '0';
	}
	for (int i = 0; i < n; i++)
	{
		cin >> str;
		for (int j = 0; j < str.length(); j++)
			b[i][j] = str[j] - '0';
	}

	int ans = 0;
	for (int i = 0; i < n - 2; i++) // 3x3 행렬씩 연산하므로 n - 2까지
	{
		for (int j = 0; j < m - 2; j++)
		{
			if (a[i][j] != b[i][j]) // 현재 인덱스의 원소가 서로 다르다면 연산 수행
			{
				reverse33(i, j);
				ans++;
			}
		}
	}

	for(int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] != b[i][j]) // 행렬을 비교하여 다르다면 -1
			{
				ans = -1;
			}
		}
	cout << ans << '\n';
}

백준 1080번 행렬

Baekjoon algorithm