[백준 C++] 1080번 - 행렬

문제 소개

 

1080번: 행렬

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

 

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

 

 

---

문제 풀이 전략

 

기획

 

 언뜻보면 여러 경우의 수를 모두 따져보아야 하는 복잡한 문제 같지만 전혀 그렇지 않다.

 

 예를 들어서 x = 0, y = 0 위치에 있는(모서리에 있는) A의 원소가 B의 원소와 다르다고 가정해 보자. 이 원소를 B의 원소와 같게 하려면 당연하게도 x = 0 1 2, y = 0 1 2에 있는 원소를 모두 뒤집는 방법 말고는 없다.

 

 이러한 논리로 모서리에서 시작하여 한점씩 한 점씩 나아가며 어떤 좌표 (n, m) 위치에 있는 A의 원소와 B의 원소가 다를 경우에 x = n n+1 n+2, y = m m+1 m+2 위치의 모든 A점을 뒤집어 나가면 이 문제를 해결할 수 있다.

 

 

---

소스 코드

 

#include <iostream>
using namespace std;

void scanData();
void solveProblem();
void printAnswer();
void printStart(); //디버깅용

char start[50][50];
char goal[50][50];
int n, m;
int ans = 0;

int main()
{
    scanData();
    solveProblem();
    printAnswer();

    return 0;
}

void scanData()
{
    char tmp;
    scanf("%d %d", &n, &m);
    scanf("%c", &tmp);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%c", &start[i][j]);
        }
        scanf("%c", &tmp);
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%c", &goal[i][j]);
        }
        scanf("%c", &tmp);
    }
}

void solveProblem()
{
    for(int i = 0; i < n - 2; i++)
    {
        for(int j = 0; j < m - 2; j++)
        {
            if(start[i][j] == goal[i][j])
                continue;

            for(int x = i; x < i + 3; x++)
            {
                for(int y = j; y < j + 3; y++)
                {
                    if(start[x][y] == '1')
                        start[x][y] = '0';
                    else
                        start[x][y] = '1';
                }
            }

            ans += 1;
        }
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(start[i][j] != goal[i][j])
            {
                ans = -1;
                return;
            }
        }
    }
}

void printAnswer()
{
    cout << ans << endl;
}

void printStart() //디버깅용
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            cout << start[i][j] << " ";
        cout << endl;
    }
    cout << endl;
}