[C++][BOJ 1080 행렬] 그리디

boj 행렬

 

문제 풀이

문제를 처음에 딱 읽고 이해 바로 못했다.

 

애해한 부분을 다른 분들 설명 보며 조건에 대해 확실히 이해했다.

- 3X3의 변환 행렬은 크기가 고정되어 있고,

- 주어진 행렬 안에만 적용된다. (3X3 필터가 주어진 행렬 내부로만 슬라이딩 가능하단 의미)

 

따라서 먼저 주어진 행렬의 크기가 3,3 이상인지 확인하고 두 갈래로 진행한다.

1. 3X3 미만이라면 두 행렬 바로 비교

2. 3X3 이상이라면 0~n-3, 0~k-3 까지 돌며 필터 적용하며 같은지 확인(주의할 점은 전체 다 돌린다음 같은지 확인이 아니라 필터 적용할 때마다 확인)

 

 

 

소스 코드

#include <bits/stdc++.h>
#define MAX 50
using namespace std;
int n,k,ans=0;
int A[MAX][MAX],B[MAX][MAX];

void InvertMatrix(int y,int x ){
	for(int dy = 0 ; dy < 3;dy++){
		for(int dx = 0 ; dx<3;dx++){
			A[y+dy][x+dx] = 1-A[y+dy][x+dx];
		}

	}
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	bool isSame;
	cin>>n>>k;

	for(int i = 0 ; i<n ; i++){
		string line;
		cin >>line;
		for(int j = 0 ;j<k;j++){
			A[i][j] = line[j] -'0';
		}
	}
	for(int i = 0 ; i<n ; i++){
		string line;
		cin >>line;
		for(int j = 0 ;j<k;j++){
			B[i][j] = line[j] -'0';
		}
	}
	

	//3x3 이상 
	if(n>=3 &&k>=3){
		for(int i =0 ;i < n-2;i++){
			for(int j = 0 ; j < k-2 ;j++){
				if(A[i][j] != B[i][j]) {
					InvertMatrix(i,j);
					ans++;
				}
			}
		}
	
	}  
	//같은지 확인   
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ;j<k;j++){
			if(B[i][j] != A[i][j] ){
				cout<<"-1";
 				return 0;
			}
		}
	}
	cout<<ans;

	
}

 

숫자 하나 하나 입력 받으면 시간 초과될까봐 string으로 한번에 받음.

 

 

참고

https://jaimemin.tistory.com/728

https://while-programming.tistory.com/33