백준 1080 - 행렬

www.acmicpc.net/problem/1080

1080번: 행렬

한번 연산하면 3X3 부분행렬의 숫자가 0이면 1, 1이면 0으로 바뀐다고 할 때 필요한 연산의 최솟값을 구하는 문제이다.

 

3X3 부분행렬만 연산이 가능하므로 행렬의 전체 인덱스를 벗어나서 연산하는 일이 없도록 해야한다.

 

 

부분행렬 연산은 현재 인덱스 (i, j)에 대해 다음 범위로 계산한다고 하자.

i, j	i, j + 1	i, j + 2
i + 1, j	i  + 1, j + 1	i + 1, j + 2
i + 2, j	i + 2, j + 1	i + 2, j + 2

이 문제는 matrix[i][j]의 원소가 한번 원하는 상태로 놓이면 더이상 바꾸지 않는 것이 최적해에 도달 할 수 있는 조건에 충족됨을 이해해야 한다.

 

자연수 $x <= 2, y <= 2$ 일 때

해당 인덱스(i, j)에 대해 원하는 상태로 만들고 나면 다음 인덱스(i + x, j + y)로 넘어갈 때 인덱스(i, j)는 인덱스 (i + x, j + y)에 대해 영향을 미치지 않는다는 점에서 탐욕적 속성을 만족한다.

 

그리고 다음 인덱스로 넘어간 시점에서 인덱스(i, j)는 최적 부분 구조를 만족했으므로 해당 인덱스의 값만 신경쓰는 그리디 방법을 적용할 수 있음을 알 수 있다.

 

이 전략에 따라 반복문을 돌며 matrix[i][j]의 원소를 바꿀지 말지 결정하는 문제로 바꾸어 해당 인덱스의 상태가 구하려는 행렬의 인덱스의 상태와 같아지도록 연산을 수행한다.

 

물론 연산은 3X3 부분행렬에 대해 적용해야 한다는 사실을 잊어서는 안되겠다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int cur[50][50];
int goal[50][50];
int click[2] {1, 0};

int r, c;

bool issame();

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    (cin >> r >> c).get();
    
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
            cur[i][j] = cin.get() - 48;
        cin.get();
    }
    
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
            goal[i][j] = cin.get() - 48;
        cin.get();
    }
    
    if (r < 3 || c < 3)
    {
        if (!issame())
        {
            cout << -1;
            return 0;
        }
        
        cout << 0;
        return 0;
    }
    
    int cnt = 0;
    
    for (int i = 0; i <= r - 3; ++i)
    {
        for (int j = 0; j <= c - 3; ++j)
        {
            if (cur[i][j] == goal[i][j])
                continue;
            
            ++cnt;
            for (int k = i; k < i + 3; ++k)
                for (int s = j; s < j + 3; ++s)
                    cur[k][s] = click[cur[k][s]];
        }
    }
    
    if (issame())
        cout << cnt;
    else
        cout << -1;
}

bool issame()
{
    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            if (cur[i][j] != goal[i][j])
                return false;
    return true;
}

이 코드에서는 전체 행렬의 크기가 3X3이 안될 때 연산없이 두 행렬이 같은지 Base case를 체크했는데 굳이 안해도 다음 for문의 조건에 의해 올바르게 답을 구할 수 있다.