Beakjoon 1080 행렬

19 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1080

나의 풀이

InputA	InputB	XOR output
0	0	0
0	1	1
1	0	1
1	1	0

xor는 2개의 input 값이 같으면 그 결과가 0이 되고, 다르면 1이 된다.
즉 행렬 A와 B를 xor 연산을 수행한다면 A와 B의 값이 같은 원소는 0이 되고 다른 원소는 1인 행렬이 만들어진다.

A				xor	B				=	C
0	0	0	0		1	0	0	1		1	0	0	1
0	0	1	0		1	0	1	1		1	0	0	1
0	0	0	0		1	0	0	1		1	0	0	1

결국 3*3 크기의 행렬을 변환하는 연산으로 행렬 C의 값을 모두 0으로 만드는 것이 A와 B가 같아지게 되는 것이다.

이제 연산의 횟수의 최솟값을 구해보자
확실하게 행렬 C를 0으로 만드는 방법은 좌측 상단부터 연산을 수행하는 것이다.

이 때 주의할 점은 연산의 최소 크기가 3*3인 것과 연산을 한번도 하지 않아도 처음부터 A와 B가 같을 수 있다는 것을 알아야한다.

풀이 코드 : 1080 행렬

#include <stdio.h>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

int compare[50][50];

int main(){
    vector<string> A;
    vector<string> B;
    int N, M, bit;
    scanf("%d %d", &N, &M);
    A.resize(N+1);
    B.resize(N+1);

    for(int i=0;i<N;i++){
        cin>>A[i];
    }         

    for(int i=0;i<N;i++){
        cin>>B[i];
        for(int j=0;j<M;j++){
            compare[i][j] = A[i][j] -'0' ^  B[i][j] -'0';
        }
    }

    int answer = 0;
    if(N>=3 && M>=3){
        for(int i=0;i<N-2;i++){
            for(int j=0;j<M-2;j++){
                if(compare[i][j] == 1){
                    answer++;
                    for(int y=0;y<3;y++){
                        for(int x=0;x<3;x++){                 
                                compare[y+i][x+j] = compare[y+i][x+j] ^ 1;
                        }
                    }
                }
            }
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
        {
            if(compare[i][j] == 1){
                answer = -1;
                break;
            }
        }
    }
    
    printf("%d",answer);
}

채점결과