[BOJ] 행렬 - Compy's Blog

행렬

TimeLimit	MemoryLimit	Condition	TAG
2s	128MB	1 ≤ N, M ≤ 50	Greedy

먼저 문제를 읽고서 제가 준비한 시각화를 한번 영상으로 확인해 봅시다.

지금보면 어떤 알고리즘으로 가느냐.. 바로 3*3에서 제가 보고있는 것은 바로

example1

이 좌상단 입니다. 여기서 →, ↓ 을 우선순위로 오른쪽으로 갈 수 있다면 즉 m(가로)가 현재 위치보다 2이상 크다면 한번 검사를 하는데 현재 자기 자신 위치가 정답 행렬과 다르다면 반전 시킵니다.

왜 이렇게 할까요??

이유는 일단 탐색 방향이 절대로 왼쪽이나 위로 올라가지 않고 딱 한번 보고서 처리를 진행할 겁니다. 그때 정답을 맞추려면 하나도 틀리면 안되기에 내가 있는 위치는 이제 마지막으로 보는 순서겠죠? 지금 보고있다면 말이죠.

그래서 내가 다르면 일단 반전을 시켜야 정답에 가까워질 수 있습니다. 만약 “나는 한번에 처리해아한다고 생각해! 왜냐하면 문제에서 최소로 반전시킨 횟수를 반환해야 하니까!”

뭔가 한번에 처리될 수 있는 경우는 이미 위에서 내려오면서 됐을 겁니다. 만약 위에서 또 변경될 값이 있다면 다시 반전되겠지만, 무조건 우리는 될 수 있다에 가까워져야 되기 때문에 이렇게 반전을 하는거구요. 이 과정에서 이 경우가 최소가 될 수 밖에 없게 됩니다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int board[51][51];
int answer[51][51];
int n, m;

void change(int y, int x){
    for(int i = y; i < y+3; i++){
        for(int j = x; j < x+3; j++){

            board[i][j] = !board[i][j];
        }
    }
}


bool check(){

    for(int i = 0; i < n; i++){
        for(int j = 0;  j < m; j++){
            if(board[i][j] != answer[i][j]) return false;
        }}

    return true;
    }

    

int solve() {
   int result = 0;

    for(int i = 0; i < n-2; i++){
        for(int j = 0; j < m-2; j++){
        
            if(check()) return result;
            if(board[i][j] == answer[i][j])
                continue;
            change(i, j);
            result++;
        }}

   if(check()) return result;
   else return -1;
   
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    char tmp;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){

            cin >> tmp;
            board[i][j] = tmp - '0';
        }}

    
    for(int i = 0; i < n; i++){
        
        for(int j = 0; j < m; j++){
            cin >> tmp;
            answer[i][j] = tmp - '0';
        }}

    cout << solve();
    return 0;
}