[C++] 백준 온라인 저지 1080번 행렬 풀이

A 행렬을 뒤집어서 B 행렬로 만들 수 있을까? 없을까? 

있다면 몇 번만에 만들 수 있을까? 를 구하는 문제

 

---

 

문제의 조건

 

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

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

 

 

풀이 과정

 

 아이디어 안 떠올라서 구글링을 해 보았는데 정말 친절하게 그림으로 하나하나 설명해 놓은 블로그가 있어 여기를 참고하시면 좋습니다. 

 

https://mizzo-dev.tistory.com/entry/baekjoon1080

[백준(baekjoon) 1080] 행렬

 

1. A 행렬, B 행렬, bool 행렬을 만든다. A, B 행렬에 각각 입력 받으면서 bool 행렬에 A 행렬과 B 행렬을 비교한 결과를 저장한다. 같은 값이 들은 인덱스엔 false, 다른 값이 들은 인덱스엔 true 저장. 

 

2. bool 행렬의 (0, 0) ~ (height - 3, width - 3) 까지 3 x 3 크기씩 뒤집어가면서 횟수를 센다. 뒤집고 횟수를 세는 기준은 bool 행렬의 (i, j) 인덱스값이 true라면 해당 인덱스부터 가로+3 세로+3 인덱스까지 뒤집어준다. false라면 통과.

 bool 행렬이 모두 false로 바뀌면 두 행렬을 똑같이 만들 수 있는 것이다. 

 

3. 만약 행렬 크기가 3 x 3보다 작으면 뒤집기 연산 자체가 불가능하기 때문에 두 행렬의 크기가 같으면 0을 출력하고 다르면 -1을 출력한다. 

 

 

코드

 

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

using namespace std;

int main()
{
    int height, width;
    cin >> height >> width;
    
    vector<vector<int>> matrixA(height, vector<int>(width, 0));
    for (int i = 0; height > i; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; s.length() > j; j++)
            matrixA[i][j] = s[j] - '0'; //입력이 char라 아스키코드의 0을 빼줘야 int로 형변환 됨
    }
    
    vector<vector<int>> matrixB(height, vector<int>(width, 0));
    vector<vector<bool>> check(height, vector<bool>(width, false));
    for (int i = 0; height > i; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; s.length() > j; j++)
        {
            matrixB[i][j] = s[j] - '0';
            if (s[j] - '0' != matrixA[i][j])
                check[i][j] = true;
        }
    }
    
    int answer = 0;
    if (3 <= height && 3 <= width)
    {
        for (int i = 0; height - 2 > i; i++)
        {
            for (int j = 0; width - 2 > j; j++)
            {
                if (check[i][j]) //true면 바꿔야 됨
                {
                    answer++;
                    for (int k = i; i + 3 > k; k++)
                    {
                        for (int l = j; j + 3 > l; l++)
                            check[k][l] = !check[k][l];
                    }
                }
            }
        }
        
        for (int i = 0; check.size() > i; i++)
        {
            for (int j = 0; check[i].size() > j; j++)
            {
                if (check[i][j])
                {
                    //하나라도 true가 있으면 똑같게 만들 수 없는 것임 
                    answer = -1;
                    break;
                }
            }
        }
    }
    else
    {
        //입력 크기가 3*3보다 작으면 뒤집기 연산 자체가 불가능하기 때문에
        //같으면 0 출력, 다르면 -1 출력 
        if (matrixA == matrixB)
            answer = 0;
        else
            answer = -1;
        
    }
    
    cout << answer;
    
    return 0;
}