24778 Cracking The Safe

많은 고민을 했는데도 결국 생각해내지 못했다.. 그런데 언젠가 푼 적이 있는 것 같다?

생각해보니 십자뒤집기 문제와 비슷했다. 경우의 수가 얼마 없으니 모든 뒤집는 경우를 다 구해보고 풀면 되겠다 싶었다. 

 

https://burningjeong.tistory.com/616

10472 십자뒤집기

 

이처럼 9개밖에 안 될 때는 모든 경우로 문제를 풀 수 있다는 걸 떠올려보자. 

그런데 이전 문제 풀 때와 다른 점이 있었다. 바로 0, 1로 이루어진 게 아니라 0, 1, 2, 3으로 이루어져있다. 

그래서 그냥 모든 버튼을 누르는 경우, 뒤집는 경우를 구해서 풀었는데 틀렸다...

한 버튼을 여러 번 누를 수 있다는 조건을 놓쳤다. 

그럼 한 버튼을 최대 3번을 누를 수 있으니 이것도 비트마스크로 풀고 싶었다. 00, 01, 10, 11이니 두 자리 비트로 계산하면 되지 않을까 싶었는데 맞는지 모르겠다. 특히 비트가 1 증가하는 경우를 어떻게 처리하지 고민이었다. 

나중에 다시 풀어봐야겠다. 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

vector<string> getFlipList() {
    vector<string> flipList = {"111100100", "111010010", "111001001", 
                                        "100111100", "010111010", "001111001", 
                                        "100100111", "010010111", "001001111"};
    return flipList;
}



int main() {
    vector<string> flipList = getFlipList(); // 십자로 뒤집는 경우들
    
    vector<int> v(9);
    for (int i = 0; i < 9; i++) {
        scanf("%d", &v[i]);
    }
    
    int ans = 100;
    for (int i = 0; i < (1 << 9); i++) {
        string BitToBeFlipped = "000000000";
        int count = 0; // 총 몇 번 뒤집는지
        
        for (int j = 0; j < 9; j++) {
            if (!(i & (1 << j)))
                continue;
            count++;
            BitToBeFlipped[j] = '1'; // j번째 비트맵을 뒤집는다
        }
        
        // 칸 뒤집기
        vector<int> copyV = v;
        for (int i = 0; i < BitToBeFlipped.size(); i++) {
            if (BitToBeFlipped[i] == '0') 
                continue;
            
            // 뒤집는다
            // "111100100"
            for (int j = 0; j < flipList[i].size(); j++) {
                if (flipList[i][j] == '0')
                    continue;
                
                copyV[j] = (copyV[j] + 1) % 4;
            }
        }
        
        
        // 결과가 전부 0이라면
        bool check = true;
        for (int i = 0; i < copyV.size(); i++) {
            if (copyV[i] != 0)
                check = false;
        }
        
        if (check)
            ans = min(ans, count);
    }
    
    if (ans == 100) {
        printf("-1\n");
    } else {
        printf("%d\n", ans);
    }
    
    return 0;
}

 

백트레킹으로 풀었다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

vector<string> flipList = {"111100100", "111010010", "111001001", 
                                        "100111100", "010111010", "001111001", 
                                        "100100111", "010010111", "001001111"};
vector<int> v(9);
int ans = 100;

bool isAllZero() {
    for (int i = 0; i < v.size(); i++) {
        if (v[i] != 0)
            return false;
    }
    return true;
}

void flip(int idx, int filpCount) {
    for (int i = 0; i < flipList[idx].size(); i++) {
        if (flipList[idx][i] == '0')
            continue;
        v[i] = (v[i] + filpCount) % 4;
    }
}

void printVector(vector<int> &v) {
    for (int i = 0; i < v.size(); i++) {
        if (i % 3 == 0)
            printf("\n");
        printf("%d ", v[i]);
    }
    printf("\n");
}

void solve(int idx, int cnt) {
    if (isAllZero()) {
        // printf("all zero: %d\n", cnt);
        ans = min(ans, cnt);
    }
    
    if (idx == 9) {
        return;
    }
    
    // printVector(v);
    
    vector<int> original = v;
    for (int i = 0; i < 4; i++) {
        flip(idx, i);
        solve(idx + 1, cnt + i);
        v = original;
    }
}

int main() {
    for (int i = 0; i < v.size(); i++) {
        scanf("%d", &v[i]);
    }
    
    solve(0, 0);
    
    ans = ans == 100 ? -1 : ans;
    printf("%d", ans);
    
    return 0;
}