후보키

https://programmers.co.kr/learn/courses/30/lessons/42890

백트래킹을 실행하면

1 2 3

1 3

2 3

이런 식으로 vv 벡터에 저장되고

이것을 

1 3 

2 3

1 2 3

sort를 통해 위처럼 바꿔줘야 한다. (짧은 것이 우선이므로)

그 다음

1 2 3 안에 1 3이 포함되었는지 검사해야 한다.

그리고 answer을 증가시키면 안 되므로,

visit 배열을 통해 탈락된 배열의 인덱스 번호에 대하여 방문 여부를 처리하여 answer을 셈한다.

#include <bits/stdc++.h>
 
using namespace std;
 
bool c[10];
int answer = 0;
vector<int> v;
bool visit[100100];
vector< pair<int, vector<int> > > vv;
 
void backtracking(vector<int> vc, int idx, vector<vector<string> > relation)
{
    if (vc.size() >= 2)
    {
        map<string, int> m;
        bool stop = true;
 
        for (int i = 0; i < relation.size(); i++)
        {
            string k = "";
            for (auto j : vc) k += relation.at(i).at(j);    
            if (m.count(k)) { stop = false; break; }            
            m[k] = 1;
        }
 
        if (stop) 
        { 
            vv.push_back({vc.size(), vc}); 
            return; 
        }
    }
 
    for (int i = idx; i < v.size(); i++)
    {
        vc.push_back(v.at(i));
        backtracking(vc, i + 1, relation);
        vc.pop_back();
    }
}
 
bool chk(vector<int> S, vector<int> B)
{
    int cnt = 0;
 
    for (auto i : S)
        for (auto j : B)    
            if (i == j)
            {
                ++cnt;
                break;
            }
 
    if (cnt == S.size()) return false;
    return true;
}
 
int solution(vector<vector<string>> relation) 
{
    // 1개
    for (int i = 0; i < relation.at(0).size(); i++)
    {
        bool go = true;
        map<string, int> m;
 
        for (auto row : relation)
        {
            if (m.count(row.at(i)))
            {
                go = false;
                break;
            }
            else m[row.at(i)] = 1;
        }
 
        if (go)
        {
            c[i] = true;
            ++answer;
        }
    }
 
    for (int i = 0; i < relation.at(0).size(); i++)
        if (!c[i])
            v.push_back(i);
 
    vector<int> vc;
 
    backtracking(vc, 0, relation);
 
    sort(vv.begin(), vv.end());
 
    for (int i = 0; i < vv.size(); i++)
    {
        if (visit[i]) continue;
 
        ++answer;
 
        for (int j = i + 1; j < vv.size(); j++)
            if (!chk(vv.at(i).second, vv.at(j).second))
                visit[j] = true;
    }
 
    return answer;
}
 
int main(void)
{
    /*vector<vector<string> > vs = {
        {"100", "ryan",   "music",    "2"}, 
        {"200", "apeach", "math",     "2"}, 
        {"300", "tube",   "computer", "3"}, 
        {"400", "con",    "computer", "4"}, 
        {"500", "muzi",   "music",    "3"}, 
        {"600", "apeach", "music",    "2"}
    };*/
 
    vector<vector<string> > vs = {
        { "a", "A", "1", "4" },
        { "b", "B", "2", "4" },
        { "c", "A", "1", "6" }
    };
 
    printf("%d\n", solution(vs));
 
    return 0;
}