[백준 알고리즘/C++/그리디] 1080 행렬

 

 

0과 1로만 이루어진 행렬 A, B가 주어졌을 때,

행렬을 변환하는 연산(3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것)을 통해 A를 B로 만드는 문제

 

 

A와 B를 입력받고 두 행렬의 원소가 다른 곳을 체크해준다 (아래 코드의 check)

원소가 다르다 = 뒤집어야 한다 = check의 true로 표시

그러므로 true인 곳들을 모두 false로 뒤집어주어야 두 배열이 일치한 게 된다

 

이제 그냥 true면 3*3 영역의 원소를 뒤집어주면 되는데,

속도를 위해서 중간중간 무조건 -1이 되는 경우를 확인해야 한다

i행의 가장 끝 두 열을 확인하면 되는데.. 거긴 앞으로 바뀔 일이 없으니 그곳이 true라면 break 해버리자

그리고 꼭 n이나 m이 3 미만일 경우도 생각해줘야 한다

 

그림 없이는 설명이 어려운데... 참고한 블로그ㅠ

[백준(baekjoon) 1080] 행렬

 

 

마지막으로 true가 있는지 모두 살펴보고 count한 값을 출력하면 된다

 

 

#include <iostream>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, m, res = 0;
    char ele; //element
    bool a[50][50], b[50][50], check[50][50] = { 0, };
 
    cin >> n >> m;
 
    //a
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> ele;
            a[i][j] = (ele == '1');
        }
    }
 
    //b
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> ele;
            b[i][j] = (ele == '1');
        }
    }
 
    //check
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] != b[i][j]) check[i][j] = 1;
        }
    }
 
    if (n < 3 || m < 3) { //n이나 m이 3 미만
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (check[i][j] == 1) {
                    res = -1;
                    break;
                }
            }
        }
    }
    else {
        //뒤집기
        int i, j;
        for (i = 0; i <= n - 3; i++) {
            for (j = 0; j <= m - 3; j++) {
                if (check[i][j] == 1) {
                    res++;
                    for (int k = i; k <= i + 2; k++) {
                        check[k][j] = !check[k][j];
                        check[k][j+1] = !check[k][j+1];
                        check[k][j+2] = !check[k][j+2];
                    }
                }
            }
 
            //i행 가장 끝, 끝에서 두번째 수가 true면 무조건 -1
            if (check[i][j - 1] == 1 || check[i][j - 2] == 1) {
                res = -1;
                break;
            }
        }
 
        //true인 요소가 있는지
        for (i = 0; i < n; i++) {
            if (res == -1) break;
            for (j = 0; j < m; j++) {
                if (check[i][j] == 1) {
                    res = -1;
                    break;
                }
            }
        }
    }
 
    cout << res;
}

 

꼴도 보기 싫은 코드가 완성됐다.. a, b, check 다 따로 만들 필요도 없어 보이고 수정하고 싶은데

지금 엄마가 숭어회 사왔으니까 그거 먹으러 가야한다