1080번 행렬

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

맨 처음에 어렵게 생각하였다.(feat. 정답률)

문제를 보고, 백트래킹으로 하려고 했으나, 역시 시간 초과가 떴다.(예상)

그래서 단순 이중 for문으로 바꿔주고, 구현했더니 맞았다.

시간 초과

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m, ans = INT32_MAX;
 
vector<vector<int> > from, to;
 
bool chk(vector<vector<int> > v)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (v[i][j] != to[i][j]) {
                return false;
            }
        }
    }
    return true;
}
 
vector<vector<int> > convert(vector<vector<int> > v, int r, int c)
{
    for (int i = r; i <= r + 2; i++) {
        for (int j = c; j <= c + 2; j++) {
            v[i][j] = abs(v[i][j] - 1);
        }
    }
    return v;
}
 
void bt(vector<vector<int> > v, int y, int x, int cnt)
{
    if (x == m - 2) {
        ++y;
        x = 0;
    }
 
    if (y >= n - 2) {
        if (chk(v)) {
            ans = min(ans, cnt);
        }
        return;
    }
 
    for (int j = x; j < m - 2; j++) {
        vector<vector<int> > g = convert(v, y, j);
        bt(g, y, j + 1, cnt + 1);
    }
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d %d", &n, &m);
    
    for (int k = 0; k < 2; k++) {
        for (int i = 0; i < n; i++) {
            vector<int> temp;
            int input;
            for (int j = 0; j < m; j++) {
                scanf("%1d", &input);
                temp.push_back(input);
            }
            if (!k) {
                from.push_back(temp);
            }
            else {
                to.push_back(temp);
            }
        }
    }
 
    bt(from, 0, 0, 0);
 
    printf("%d\n", ans == INT32_MAX ? -1 : ans);
 
    return 0;
}

정답 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
 
vector<vector<int> > from, to;
 
bool chk(vector<vector<int> > v)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (v[i][j] != to[i][j]) {
                return false;
            }
        }
    }
    return true;
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d %d", &n, &m);
    
    for (int k = 0; k < 2; k++) {
        for (int i = 0; i < n; i++) {
            vector<int> temp;
            int input;
            for (int j = 0; j < m; j++) {
                scanf("%1d", &input);
                temp.push_back(input);
            }
            if (!k) {
                from.push_back(temp);
            }
            else {
                to.push_back(temp);
            }
        }
    }
 
    int cnt = 0;
 
    for (int i = 0; i < n - 2; i++) {
        for (int j = 0; j < m - 2; j++) {
            if (from[i][j] == to[i][j]) continue;
 
            for (int r = i; r <= i + 2; r++) {
                for (int c = j; c <= j + 2; c++) {
                    from[r][c] = abs(from[r][c] - 1);
                }
            }
 
            ++cnt;
 
            if (chk(from)) {
                printf("%d\n", cnt);
                return 0;
            }
        }
    }
    
    if (chk(from)) printf("0\n");
    else printf("-1\n");
 
    return 0;
}