[그리디 알고리즘] 행렬

예제 입력 1

3 4

0000

0010

0000

1001

1011

1001

예제 출력 1

2

 

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

1080번: 행렬

- 여기서, A행렬에서 모두 가능한 3x3 Flip 연산을 하느냐/하지 않느냐로 Brute Force를 돌리면 2^NM (실제로는 2^(N-2)(M-2)) 이라는 어마어마한 시간 복잡도가 나오기 때문에 이 방법으로는 해결 불가능하다.

 

- 여기서, 핵심은 (0,0) 부분이 다르다면, (0,0) 부분을 변경하도록 해야 하는데, 이 방법은 좌측 최상단부터 3x3을 뒤집는것 단 한가지 방법 밖에 없으므로 이 Flip 연산을 처리해야만 한다. 이 부분을 처리하고 나면 (0,1)도 마찬가지이다. 같으면 Flip 하지 않아야 한다. 이런식으로 0 ~ (R-2), 0 ~ (C-2)까지 반복하여 처리할 수 있다.

- 그래서 A과 B의 원소들을 모두 비교해 모두 같으면 A를 B로 바꿀 수 있는 것이고 아니라면 불가능한 것이다.

#include <stdio.h>

const int MAX_SIZE = 50;

int R, C;
int firstMatrix[MAX_SIZE][MAX_SIZE];
int secondMatrix[MAX_SIZE][MAX_SIZE];

void flip(int matrix[][MAX_SIZE], int r, int c)
{
	int rLimit = r + 3;
	int cLimit = c + 3;

	for (int i = r; i < rLimit; i++)
	{
		for (int j = c; j < cLimit; j++)
		{
			matrix[i][j] = 1 - matrix[i][j];
		}
	}
}

int main(void)
{
	int ans = 0;

	scanf("%d %d", &R, &C);

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			scanf("%1d", &firstMatrix[i][j]);
		}
	}

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			scanf("%1d", &secondMatrix[i][j]);
		}
	}
	
	for (int i = 0; i < (R - 2); i++)
	{
		for (int j = 0; j < (C - 2); j++)
		{
			if (firstMatrix[i][j] != secondMatrix[i][j])
			{
				flip(firstMatrix, i, j);
				ans++;
			}
		}
	}

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (firstMatrix[i][j] != secondMatrix[i][j])
			{
				printf("-1\n");
				return 0;
			}
		}
	}

	printf("%d\n", ans);

	return 0;
}