[DFS] (프로그래머스 Lv 2) 후보키

문제

• 문제 링크
• 문제 설명: 릴레이션에 모든 row 가 유니크하도록 하는 컬럼 조합의 개수 반환
  • 어떤 컬럼 조합에 대해 데이터들 중 같은 데이터가 없으면 그 컬럼 조합은 후보키가 될 수 있다.
  • 어떤 컬럼 조합을 포함하는 컬럼 조합은 후보키가 될 수 없다. -> 최소성
• 입력
  • relation은 2차원 문자열 배열
  • relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타냄
  • relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타냄
  • relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있음
  • relation의 모든 튜플은 유일하게 식별 가능 (즉, 중복되는 튜플은 없다.)
• 출력: 컬럼 조합의 개수

relation	result
[["100","ryan","music","2"], ["200","apeach","math","2"], ["300","tube","computer","3"], ["400","con","computer","4"], ["500","muzi","music","3"], ["600","apeach","music","2"]]	2

풀이

• relation을 이용해서 컬럼마다 데이터를 저장 -> 인덱스: 컬럼명, 값: 해당 컬럼의 데이터 목록
• 컬럼은 최대 8개 있으므로 DFS 를 이용해서 컬럼별 데이터를 조합해서 중복되는 데이터가 없으면 후보키 목록에 추가
  • "1번 컬럼 -> 2번 컬럼" 순서로 조합하는 것과 "2번 컬럼 -> 1번 컬럼" 순서로 조합하면 결과가 같으므로 인자로 현재 조합할 시작 컬럼을 추가해서 중복을 방지
  • 컬럼 개수가 8개이므로 정수형 변수에 비트로 조합한 컬럼 목록 저장 가능
• 최소성을 만족하는지 찾기 위해, 현재 중복 데이터가 없는 후보키가 이전에 후보키 목록들 중에 포함되는지 검사
  • 후보키 목록들 중 현재 후보키를 포함하는 것들이 있으면 모두 제거
  • 예를 들어, 0 1 2 … 순서로 조합을 만들다 보니 뒤에 5 7 만 있으면 후보키가 되는 경우 앞에 만들어진 후보키들을 없애야 함. 예를 들어 0 1 5 7 이 있고 0 2 3 5 7 이 있으면 둘 다 없애고 5 7만 저장
• 끝으로 후보키 목록의 크기를 반환

#include <string>
#include <vector>
#include <set>
using namespace std;

vector<string> relation_by_col[8]; // 컬럼별 데이터
int num_cols, num_rows;
set<int> candidates; // 후보키 목록

// c := 컬럼 인덱스
// cand := 조합된 컬럼 인덱스를 비트로 저장한 정수형 변수
// comb := 조합된 컬럼의 데이터들
void dfs(int c, int cand, vector<vector<string>>& comb) {
    if (comb.size() > 0) { // 하나라도 조합된 컬럼이 있으면
        set<string> s;
        for (int i = 0; i < num_rows; i++) {
            string data;
            for (int j = 0; j < comb.size(); j++)
                data += comb[j][i] + " ";
            s.insert(data);
        }
        // 데이터가 중복이 없는지 검사
        if (s.size() == num_rows) {
            // 현재 후보키를 포함하는 후보키들은 모두 제거
            while (1) {
                bool minimality = true;
                for (auto& c : candidates) {
                    if ((c & cand) == cand) {
                        candidates.erase(c);
                        minimality = false;
                        break;
                    }
                }
                // 최소성을 만족하면 break
                if (minimality) break;
            }
            candidates.insert(cand); // 후보키에 추가
            return;
        }
    }
    
    for (int i = c; i < num_cols; i++) {
        comb.push_back(relation_by_col[i]);
        dfs(i+1, cand | (1 << i), comb); // 컬럼 조합 생성
        comb.pop_back();
    }
}

int solution(vector<vector<string>> relation) {
    int answer = 0;
    num_rows = relation.size();
    num_cols = relation[0].size();
    for (int i = 0; i < relation.size(); i++)
        for (int j = 0; j < num_cols; j++)
            relation_by_col[j].push_back(relation[i][j]);
    vector<vector<string>> comb;
    dfs(0, 0, comb);
    answer = candidates.size();
    return answer;
}