[C++] 백준 1080 행렬

https://www.acmicpc.net/problem/1080

1080번: 행렬

 

1. 서론

 

어떻게 하는지 모르겠어서 그냥 뇌 빼고 푼 문제... 근데 이게 맞다고...?라서 더 놀라운 문제. 그리디 유형의 문제이다. 그리디도 dfs, dp 같은 것처럼 뭔가 푸는 로직이 있는 걸까 찾아봤는데 그냥 그때그때 문제에 따라 애드리브로 문제에 조건에 맞는 최적에 방법을 구하는 것이다. (모든 경우에서 최적의 경우를 구하는 것은 아니다)

 

2. 문제 풀이

 

행렬 A와 B가 주어진다. 행렬은 전부 0과 1로 이루어져 있다. 그리고 3x3단위로만 변경할 수 있는데 이때 0 -> 1, 1 -> 0으로 변경 가능하다. 이렇게 하는 것을 한 번의 연산 과정이라고 쳤을 때 행렬 A가 B가 되는 연산의 최솟값을 구하는 문제이다. 만약 불가능한 경우에는 -1을 출력한다.

 

나는 처음에 너무 막막했다. 생각나는 방법이라고는 그냥 배열을 돌면서 A,B를 비교해서 값이 다르면 그 부분에서 3x3을 변환하는 것이었다. 근데 이렇게 하면 연산의 최솟값을 구할 수 없을 것 같았다. 하지만 생각나는 방법이 이것밖에 없어서 이렇게 코드를 짰는데 의외로 테케들이 맞기 시작했다. 그래서 돌렸는데 틀렸습니다가 나왔다.

 

*고려해야 할 부분들

 

1. 3x3을 변환할때 배열의 범위(넘지 않고, 온전히 3x3)

2. 3x3이 안되는안 되는 경우는 무조건 안 되는 것이 아님. (예제 때문에 그렇게 생각했는데...)

3. 배열의 입력이 따로 들어오는게 아니라 000 이런 식으로 붙어서 들어오기 때문에 관련 처리

 

내가 풀면서 막혔던 부분은 위에 3가지 정도다. 물론 혼자서 알아챘으면 좋았겠지만 너무 확신도 없었고 감이 안 잡힌 나머지(이 풀이 방법이 아니라 내가 모르는 무슨 새로운 방법으로 짜야하는 줄 알고) 반례 검색을 엄청해서 알아낸 내용들이다. 스스로 생각해야 했다면... 아마 5시간 넘게 걸렸을지도 ㅎ

 

3. 코드 설명

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int n, m, i, j, k, l, cnt = 0;

    cin >> n >> m;

    vector<string> a, b;
    string s;

    for (i = 0; i < n; i++)
    {
        cin >> s;
        a.push_back(s);
    }
    
    for (i = 0; i < n; i++)
    {
        cin >> s;
        b.push_back(s);
    }

    for (i = 0; i < n - 2; i++)
    {
        for (j = 0; j < m - 2; j++)
        {
            if (a[i][j] != b[i][j])
            {
                for (k = 0; k < 3; k++)
                {
                    for (l = 0; l < 3; l++)
                    {
                        if (i + k < n && j + l < m)
                        {
                            if (a[i + k][j + l] == '0')
                                a[i + k][j + l] = '1';
                            else
                                a[i + k][j + l] = '0'; 
                        }
                    }
                }  
                cnt++;     
            }
        }
    }

    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            if (a[i][j] != b[i][j])
                cnt = -1;
                
    cout << cnt << endl;   
}

 

처음에는 배열로 입력받았는데 입력이 000 이런식으로 들어온다는 것을 알고 굳이 따로 찢어주기도 귀찮고 숫자로 바꿀 필요도 없는 문제라 문자열 배열로 입력받았다. 이렇게 하면 원래는 2차원 배열이지만 string이 하나의 배열이기 때문에 그냥 문자열 백터로 2차원 배열을 만들어줬다. 

 

그리고 배열을 돌면서 두 배열을 비교하는데 만약 다른 값이 나오면 그 즉시 3x3 배열을 연산하는 작업을 해준다. 이때 내가 실수했던게 그냥 배열을 다 돌아서 범위가 터졌는데(런타임 에러) 어차피 변환하려면 3x3이 최대이기 때문에 n-2 x m-2의 범위까지만 탐색을 해준다. (그 이상의 범위는 탐색해도 변환하지 못하므로) 그리고 변환할 때마다 cnt 해준다. (근데 난 이게 최적의 방법이 아닐 텐데...라고 생각했는데 이게 맞았다)

 

그리고 나와서 두 배열이 같은지 확인하고 아니면 -1을 출력한다.