알고리즘/C++
[C++] BAEKJOON 1080 행렬
ssung.k
2019. 9. 16. 00:33
https://www.acmicpc.net/problem/1080
1080번: 행렬
첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
www.acmicpc.net
그리디 알고리즘
을 사용하여 문제를 해결하였습니다.
세로에 대해서는 세로길이-2 까지, 가로에 대해서는 가로길이-2 까지 순회를 하며 행렬을 뒤집을지 말지 결정해주었습니다. (0,0) 부분에 대해서 영향을 미치는 경우는 좌측 상단 모서리에 위치한 3*3
부분 행렬을 뒤집을 때 뿐이고 이 연산을 수행한 후, (0,1) 부분에 영향을 미치는 경우는 (0,1) 부터 시작하는 3*3
부분 행렬을 뒤집을 때 뿐입니다. 때문에 세로길이-2,가로길이-2 까지 순회하며 뒤집을지 말지 결정해주면 최소연산으로 가능한지 확인할 수 있습니다.
#include <iostream>
using namespace std;
int a[50][50], b[50][50];
void matrixChange(int n,int m){
for (int i=n;i<=n+2;i++){
for (int j=m;j<=m+2;j++){
a[i][j] = 1 - a[i][j];
}
}
}
int main(int argc, const char * argv[]) {
int N,M;
cin >> N >> M;
int count = 0;
for (int i=0;i<N;i++){
for (int j=0;j<M;j++){
scanf("%1d", &a[i][j]);
}
}
for (int i=0;i<N;i++){
for (int j=0;j<M;j++){
scanf("%1d", &b[i][j]);
}
}
for (int i=0;i<N-2;i++){
for (int j=0;j<M-2;j++){
if (a[i][j] != b[i][j]){
matrixChange(i,j);
count++;
}
}
}
int flag = 0;
for (int i=0;i<N;i++){
for (int j=0;j<M;j++){
if (a[i][j] != b[i][j]){
count = -1;
flag = 1;
break;
}
}
if (flag) break;
}
cout << count << "\n";
return 0;
}