[백준] 행렬 (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을 출력한다.

예제 입력 1 복사

3 4 0000 0010 0000 1001 1011 1001

예제 출력 1 복사

2

---

그리디 문제이다.

어떻게 풀지 생각해봤는데, 그냥 제일 앞자부터 검사하며 A와 B가 다르면 switch해주고 같으면 넘어간다. 

1과 0만 다르기 때문에 같은 자리를 두 번 이상 바꿀 필요가 없기 때문에 이 방식으로 풀 수 있다.

주의할 점은 한 번 바꿀 때 3x3 크기의 행렬을 모두 switch해줘야 하기 때문에, 조사하는 범위도 N-2, M-2까지만 조사해야 한다. 코드를 보면 쉽게 이해가 될 것이다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%96%89%EB%A0%AC%20(1080%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

  
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int N, M;
int p[51][51], q[51][51];

void change(int a, int b) {
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			if (p[a + i][b + j] == 0) p[a + i][b + j] = 1;
			else p[a + i][b + j] = 0;
}

bool isPossible() {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			if (p[i][j] != q[i][j])
				return false;

	return true;
}

int main()
{
	cin >> N >> M;
	string str;
	for (int i = 1; i <= N; i++) {
		cin >> str;
		for (int j = 1; j <= M; j++)
			p[i][j] = str[j-1] - '0';
	}
	for (int i = 1; i <= N; i++) {
		cin >> str;
		for (int j = 1; j <= M; j++)
			q[i][j] = str[j-1] - '0';
	}

	int res = 0;
	for (int i = 1; i <= N-2; i++)
		for (int j = 1; j <= M-2; j++)
			if (p[i][j] != q[i][j]) {
				change(i, j);
				res++;
			}


	if (!isPossible()) cout << "-1";
	else cout << res;
	
}