백준 1080(행렬)

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

1080번: 행렬

문제를 정말 잘 읽어봐야 하는 문제.

 

이 문제에서 N*M의 행렬을 3*3의 부분행렬의 값을 1->0 0->1 로 변경하여 A와 B의 행렬이 같게 만드는 문제이다.

 

처음에 부분행렬이라고만 봐서 모든 부분행렬을 따져봐야 되나 이런 생각을 해보았다. 

 

전체탐색으로 풀려고 했다. 왜냐하면 행렬의 변환이 무작위라고 느껴졌기 때문이다. 

전체탐색 재귀로 풀게된다면 시간복잡도는 O(2^n)이므로 2^50, 약 10^17 엄청난 시간이 걸렸을 것이다. 

만약 이 문제가 greedy라는 것을 몰랐으면 아직까지 헤매고 있었을지도, 

 

문제의 핵심은 

 

어떤 값을 변경시킬 수 있는 부분행렬은 하나다. 

스도쿠 퍼즐을 맞추듯이 무작위로 보여도 하나의 값에 대한 변수는 고정되어 있고,  그 수를 고정하고 나면 나머지도 변수에 대해서 고정되어 있다는 것이다.

 

설명을 좀 자세히 하자면 행렬 0,0의 값은 0,0 0,2 2,0 2,2 로 이루어진 부분행렬로밖에 변경할 수 없다. 

따라서 0,0부터 차례대로 다르면 변경하고, 같으면 냅두고를 반복한다. 

 

그리고 마지막으로 함정일 수 있는 행렬의 크기가 3*3보다 작은 경우이다. 이 조건 또한 따져줘야 한다.

 

시간복잡도는 O(n^4)로 50^4 6,250,000 O(10^6)이다. 

 

 

당장 최선이라고 생각하는 방법이 결과적으로도 최선의 결과를 내놓는 알고리즘이다. 

그리디 알고리즘의 특성상 모든게 그리디로 보일 수 있다. 많은 문제를 풀어야 그리디인지 다른건지 판단할 수 있는 방법들도 생기지 않을까.

 

#include<iostream>
using namespace std;
#define MAX 50

int Amat[MAX][MAX];
int Bmat[MAX][MAX];
int a, b ,cnt=0;
bool check = true;


int main() {
	cin >> a >> b;

	char num;
	for (int i = 0; i < a; i++) {
		for(int j = 0; j < b; j++){
			cin >> num;
			Amat[i][j] = (num - '0');
		}
	}
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			cin >> num;
			Bmat[i][j] = (num - '0');
		}
	}
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			if (Amat[i][j] != Bmat[i][j]) {
				check = false;
			}
		}
	}
	if (check) {
		cout << cnt << "\n";
		return 0;
	}
	if (a < 3 || b < 3) {
		cout << -1 << "\n";
		return 0;
	}

	for (int c = 0; c < a - 2; c++) {
		for (int d = 0; d < b - 2; d++) {
			check = true;
			if (Amat[c][d] != Bmat[c][d]) {
				cnt++;
				for (int e = c; e < c + 3; e++) {
					for (int f = d; f < d + 3; f++) {
						Amat[e][f] = !Amat[e][f];
					}
				}
			}

			for (int i = 0; i < a; i++) {
				for (int j = 0; j < b; j++) {
					if (Amat[i][j] != Bmat[i][j]) {
						check = false;
					}
				}
			}
			if (check) {
				cout << cnt << "\n";
				return 0;
			}
		}
	}
	cout << -1 << "\n";

}