백준 1080번 행렬

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

1080번: 행렬

 

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)

 

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그다음 줄부터 N개의 줄에는 행렬 B가 주어진다.

 

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

 

풀이

이 문제와 같이 뒤집기 문제의 핵심은 동일한 뒤집기를 두 번 실행할 필요가 없다는 것이다. 똑같은걸 두 번 뒤집어 봤자 결과는 처음과 동일하기 때문이다.

행렬의 크기는 50 x 50 이기 때문에 완전 탐색으로 뒤집는 모든 경우의 수를 계산하려면 2^2500번을 해야하니 이 문제는 반드시 규칙성을 찾아야 한다.

발견한 규칙은 이러하다

그림이 조잡하긴 하지만.. 4x4 행렬에 대해서 모든 뒤집기를 실행한 결과이다.(뒤집기마다 색이 다른거임!!)

그림을 잘 보면 빨간색 부분은 처음에 딱 한번 실행한 건데 고대로 남아있는 걸 볼 수 있다.

그렇다!! 맨 위 오른쪽 부분은 원하는 행렬의 숫자와 다르면 무조건! 뒤집어야 한다.

이를 뒤집고 나면, 그다음은 노란색 처음 부분(0,1)이 빨간색과 동일한 상황에 처한다.

그다음은 주황색(1,0).. 그다음은 초록색(1,1)이 된다.

만약 이 과정을 거쳤는데도 원하는 행렬이 만들어지지 않는다면, 이 행렬은 안 되는 행렬이다.(뒤집을 건 다 뒤집은거니까..)

그렇다면 다른 크기의 행렬은 어떨까??

눈치챘겠지만, 0~(n-2) x 0~(n-2)에 속하는 칸들에 대해 위와 같은 과정을 적용하면 된다.

코드로 살펴보자!

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int a[50][50];
int b[50][50];
 
void reverse(int y, int x) {
    for (int i = y - 1; i <= y + 1; i++) {
        for (int j = x - 1; j <= x + 1; j++) {
            a[i][j] = 1 - a[i][j];
        }
    }
}
int main()
{
    //입력
    int n, m; scanf("%d%d", &n, &m);
    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]);
        }
    }
    int ans = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = 0; j < m - 2; j++) {
            if (a[i][j] != b[i][j]) {
                ans++;
                reverse(i + 1, j + 1);
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] != b[i][j]) {
                printf("%d", -1);
                return 0;
            }
        }
    }
    printf("%d", ans);
    return 0;
}

코드는 간단하다. for 0 ~ n-2 과정을 거치면서 원하는 행렬 원소와 다르면 그 부분 3x3 행렬을 뒤집으며 반복한 후,

원하는 행렬과 일치하는지 확인하면 끝!

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~