[BOJ] 1080. 행렬

 

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

1080번: 행렬

그리디 알고리즘...

매 순간마다 최적의 선택을 한다.

결론이 나왔을때 이것이 최고가 아닐수도 있다. 하지만 그렇게 푸는거다.

​

이 문제는 그리디 알고리즘인데, 가장 적게 뒤집으면서 B 행렬과 같은지 판단해야한다.

​

난 무지성인간이라 처음에 그냥 브루트포스로 다 뒤집었다.

이게 최적이 될리가 없었다.

평소에 일단 완전탐색처럼 풀고, 비효율적인걸 걷어내는식으로 했는데..

이건 그 방식으로 접근하다가 머리가 너무 아팠다. 생각을 미리 하고 했어야했다.

​

일단 난 못풀었다.

동아리에서 힌트영상을 보고 풀었다.

말이 힌트영상이지 사실상 정답수준이다.

이렇게 생각하는걸 까먹지 않기위해 남긴다.

​

핵심 :

최소한의 뒤집는 횟수에서, 내 기회일때만 뒤집을 수 있는것들만 검사하면 된다.

​

아래 예시를 보고나면 무슨말인지 이해가 갈 것이다.

​

​

예제:

before을 after로 바꾸기 위해선 2번만 뒤집으면 할 수 있다.

바로 노랑 먼저, 빨강 먼저이다. (왼 > 오)

물론 (오 > 왼) 으로 뒤집더라도 답은 똑같이 나온다.

​

방향이 중요한것이 아니다.

어짜피 최소횟수는 2번이니까 그 2번을 알맞은 곳에만 뒤집으면 되는것이다.

​

방법 1.

​

​

여기서 노란색 square을 먼저 보면, 맨 왼쪽 상단을 제외하고는 나머지는 모두 다른 차례에 뒤집어 질 수 있다.

​

'1'을 1번 뒤집으면 0이다. '0' 을 2번 뒤집으면 '1' 이다. 즉 자기 자신이 나온다.

​

3x3 square에서 '방향'이 왼>오 로 정했다면, 맨왼쪽 맨위에 있는 숫자만이 다시 뒤집을 수 없는 유일한 숫자이다.

> (최소한의 뒤집는 횟수에서, 내 기회일때만 뒤집을 수 있는것들만 검사하면 된다.)

​

만약 '방향'이 오>왼 이었다면? 맨 오른쪽 맨 위에 있는 숫자만이 다시 뒤집을 수 없는 유일한 숫자일 것이다.

​

한번 스스로 예시를 뒤집어 보면 알 것이다.

왼>오 방향의 경우 맨왼쪽 맨위, 오>왼 일 경우 맨오른쪽 맨위 만 검사하고 뒤집는다면 최소한의 횟수로 뒤집을 수 있을것이다.

​

혹시나해서 쓰지만,

초록색 동그라미쪽에서 2번째 row부터는 row가 더 길다면 뒤집어진다.

따라서 반드시 맨왼쪽 맨위에만 봐야한다는 것이다. (row가 4개 이상이면 아래 친구들도 뒤집어질 것이므로)

만약 row가 3개라면, 더이상 뒤집어 질 기회가 없으므로, 맨왼쪽 맨위를 뒤집으면 아래까지 다같이 한 것이다. (초록 동그라미 부분)

​

소스코드

#include <cstdio>
using namespace std;
typedef long long ll;
char B_A[51][51];
char B_B[51][51];
// 3 3 이상일땐 제외
int solve(int R,int C)
{
	int ans = 0;
	int flag = 0;
	int p,q;
	// 3x3 뒤집고 전체랑 비교, 만약 모두가 0과 1이 다르면 true; 아니면 계속 
	for(int i = 0; i <= R-3; i++)
	{
		for(int j = 0; j <= C-3; j++)
		{
			
			//좌상단 이 같은가 다른가	
			if(B_A[i][j] == B_B[i][j]) continue;
		
			ans++;
			for(int x = 0; x < 3; x++)
			{
				for(int y = 0; y < 3; y++)
				{
					if(B_A[i+x][j+y] == '0'){
						B_A[i+x][j+y] = '1';
					}
					else{
						B_A[i+x][j+y] = '0';
					}
				}
			}
		}
	}
	flag = 0;
	for(p = 0; p < R; p++)
	{
		for(q = 0; q < C; q++)
		{
			if(B_A[p][q] != B_B[p][q]){
				flag = 1;
				break;	
			}
						
		}
		if(flag) break;
	}
	if(p == R) return ans;
	
	return -1;
}
int main(void) 
{
	int R,C; //숫자
	
	int ans = 0;
	int flag = 0;
	int x,y;
	scanf("%d %d",&R,&C);
	
	for(int i = 0; i < 2; i++)
	{
		for(int j = 0; j < R; j++)
		{
			if(i == 0){
				scanf("%s",B_A[j]);
			}else{
				scanf("%s",B_B[j]);
			}
		}
	}	

	printf("%d\n",solve(R,C));	
    return 0;
}

---