Synchronizing Clocks

문제

https://algospot.com/judge/problem/read/CLOCKSYNC

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> v;

int clocks[16];

int min_val = 2e9;

bool is_ans() {
    for (int i = 0; i < 16; i++) {
        if (clocks[i] != 0)
            return false;
    }
    return true;
}


void dfs(int cur_idx, int cur_count, int tot_count) {
    if (cur_idx == 10) {
        if(is_ans())
            min_val = min(min_val, tot_count);
    }
    else {
        if (cur_count < 3) {
            for (int j = 0; j < v[cur_idx].size(); j++) {
                clocks[v[cur_idx][j]] = (clocks[v[cur_idx][j]] + 1) % 4;
            }

            dfs(cur_idx, cur_count + 1, tot_count + 1);

            for (int j = 0; j < v[cur_idx].size(); j++) {
                clocks[v[cur_idx][j]] = (clocks[v[cur_idx][j]] + 3) % 4;
            }
        }
        dfs(cur_idx + 1, 0, tot_count);
    }
}

int main() {

    v.push_back(vector<int>{0, 1, 2});
    v.push_back(vector<int>{3, 7, 9, 11});
    v.push_back(vector<int>{4, 10, 14, 15});
    v.push_back(vector<int>{0, 4, 5, 6, 7});
    v.push_back(vector<int>{6, 7, 8, 10, 12});
    v.push_back(vector<int>{0, 2, 14, 15});
    v.push_back(vector<int>{3, 14, 15});
    v.push_back(vector<int>{4, 5, 7, 14, 15});
    v.push_back(vector<int>{1, 2, 3, 4, 5});
    v.push_back(vector<int>{3, 4, 5, 9, 13});

    int C;
    cin >> C;
    while (C--) {


        min_val = 2e9;
        int input;
        for (int i = 0; i < 16; i++) {
            cin >> input;
            clocks[i] = (input % 12) / 3;
        }

        dfs(0, 0, 0);

        if (min_val == 2e9)
            cout << -1 << '\n';
        else
            cout << min_val << '\n';

    }


}

피드백

• 이 문제는 혼자서 풀어내지 못함
• 처음 시도할때는 순서를 고려한 완전탐색으로 dfs, bfs모두 구현하였으나 각각 시간초과, 메모리초과가 떳다.
  • 즉, 너무 많은 복잡도를 맞이함
• 답지의 해결책은 스위치 누르는 순서는 결과값에 영향을 주지 않는다는 것부터 시작된다.
  • 실제로 1,4 번 순으로 누르건 4,1번 순으로 누르건 결과값음 같다.
• 이 때문에 문제는 순열문제가 아닌 조합문제로 변하게 되고, 4^10 의 허용가능한 복잡도를 가지는 문제로 바뀐다.
• 우리가 완탐문제를 풀때, 이것이 순열로만 풀어야 하는 문제인지, 또는 조합으로 풀 수 있는 문제인지를 먼저 잘 생각하자.