백준 1080 행렬 (C++)

안유태·2023년 8월 22일
0

알고리즘

목록 보기
132/239
post-custom-banner

1080번: 행렬

그리디를 이용한 문제이다. 풀이는 단순하다. 반복문을 돌면서 배열 A와 B의 현재 위치 값이 다를 경우 현재 위치에서의 3x3만큼 A를 바꿔주면서 횟수를 카운트해주었다.. 그 후 A와 B를 비교한 후 같을 경우 횟수를 출력하고 다를 경우 -1을 출력했다. 이 문제가 왜 그리디인가에 대한 설명은 이 곳에 잘 정리가 되어있다. 그리디 문제가 생각보다 까다로운 것들이 많다. 많이 풀어봐야 겠다.



#include <iostream>

using namespace std;

int N, M;
string A[50];
string B[50];

bool same() {
    for (int i = 0; i < N; i++) {
        if (A[i] != B[i]) return false;
    }

    return true;
}

void flip(int y, int x) {
    for (int i = y; i < y + 3; i++) {
        for (int j = x; j < x + 3; j++) {
            A[i][j] = A[i][j] == '0' ? '1' : '0';
        }
    }
}

void solution() {
    int result = 0;

    for (int i = 0; i < N - 2; i++) {
        for (int j = 0; j < M - 2; j++) {
            if (A[i][j] != B[i][j]) {
                flip(i, j);
                result++;
            }
        }
    }

    if (same()) {
        cout << result;
    }
    else {
        cout << -1;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }

    solution();

    return 0;
}
profile
공부하는 개발자
post-custom-banner

0개의 댓글