프로그래머스 후보키

아이디어

• DFS를 사용할 줄 안다
• 조합 알고리즘을 사용할 줄 안다

접근방식

1. 각 요소의 개수를 1개부터 최대개수까지 dfs를 돌린다
2. dfs를 통해 각 요소를 조합으로 뽑는다
3. 조합으로 뽑는 도중에 이 안에 후보키 대상이 있는지 dfs를 한번 더 사용해서 조사한다
4. 후보키 대상이 없으면 set을 하나 만들어 각 요소와 '+'를 더한 string을 넣어준다
5. 만약 set에 중복되는 string을 찾으면 return, 끝까지 다 조사하였으면 answer에 더해주고, 각 col에 해당하는 요소들을 mini 최소성 판별 set에 저장한다

#include <string>
#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;

int answer = 0;
vector<vector<string>> new_r; // 보드 판
unordered_set<string> mini; //최소성 판별

bool mini_check_func(string temp, string s, int now_pos){
    if(temp.size() == s.size()) return false;

    for(int i=now_pos;i<s.size();i++){
        temp.push_back(s[i]);
        if(mini.count(temp)) return true;
        else{
            bool mini_temp_check = mini_check_func(temp,s,i+1);
            if(mini_temp_check == true) return true;
        }
        temp.pop_back();
    }

    return false;
}

void dfs(vector<int> pick,int max_col,string mini_check){
    if(pick.size() == max_col){
        unordered_set<string> u;
        for(int i=0;i<new_r.size();i++){
            string s="";

            for(int now_col : pick){
                s+=new_r[i][now_col];
                s.push_back('+');
            }
            if(u.count(s)) return;
            else u.insert(s);
        }
        answer++;
        mini.insert(mini_check);
        return;
    }

    int start;
    if(pick.size()) start = pick.back()+1;
    else start = 0;

    for(int i=start;i<new_r[0].size();i++){
            pick.push_back(i);
            string to_att = "";
            to_att.push_back((char)(i+'0'));
            mini_check+= to_att;

            bool is_mini = mini_check_func("",mini_check,0);

            if(is_mini == false)
            {
                dfs(pick,max_col,mini_check);
            }

            mini_check.pop_back();
            pick.pop_back();
        }
    }


int solution(vector<vector<string>> relation) {
    new_r = relation;
    vector<int> v;
    for(int i=1;i<=relation[0].size();i++){
        dfs(v,i,"");
    }
    return answer;
}

평가

아이디어가 맞다고 생각했지만, 간과한 것들을 찾을 수 있는 문제.
저 같은 경우에는 요소를 하나씩 넣으면서 그 개수만큼 최소성을 판별하였습니다.
하지만 예를들어 [1,2]에 [3]을 넣어 [1,2,3]을 만들 경우
[1][1,2] [1,2,3] 만 판별하는 것이 아닌, [3], [1,3][2,3] 도 판별 해줘야 한다는 것을 파악하지 못하였습니다.
그래서 이를 체크해주는 함수를 하나 더 만들어 사용하였습니다.
또한 재귀함수로 조합을 찾기 위해서는 for문을 돌때, 내가 뽑은 요소 + 1의 위치부터 시작하는 것을 깨달았습니다.

• 배울 것
  1) 조합 알고리즘은 뽑은 요소 + 1을 for문 시작으로 해주면 된다
  2) 요소를 check 해줄 때 적어가면서, 전부 체크해주는 것이 맞는지 판별한다