[프로그래머스][DFS] 후보키

문제

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하시오.

문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/42890)

풀이

이 문제도 지난 하반기 때 못풀었었는데 그 당시 생각했었던 방법으로 새로 풀었습니다. 후보키는 유일성과 최소성을 만족해야하기 때문에 가능한 모든 조합을 구한 다음 각 조합이 유일성과 최소성을 만족하는지 그대로 구현해서 확인하면됩니다. 당시에는 그 모든 조합을 확인할 수 있을지에 대한 의문이 있어서 다른 문제를 먼저 풀었던 것 같은데 다시 풀면서 조건을 보니 최대 column의 수와 row 수가 작기 때문에 모든 경우에 대해서 확인해볼 수 있겠다는 생각이 들었습니다. 조합을 만들기 위해서는 dfs를 사용했고 유일성을 판단하기 위해서는 유연하게 연산할 필요가 있어 파이썬을 사용하여 구현하였습니다. 파이썬의 딕셔너리를 사용하고자 했는데 리스트로도 해당 row가 있는지를 확인할 수 있기 때문에 리스트를 사용했습니다. 우선 첫번째는 dfs를 통해서 가능한 조합을 만듭니다. 그리고 그 조합을 정렬해서 길이가 작은 조합들을 먼저 시도해야합니다. 왜냐면 각 조합에 대해 시도를 할 때 이미 가능한 후보키의 부분집합이 아니어야함을 확인해야하는데 길이를 고려하지 않고 사전순으로(sort함수를 통해) 정렬하게 되면 [0], [0, 1], [1] 과 같은 순서가 되기 때문에 [1] 이 후보키가 되어야하는데 [0, 1] 이 먼저 후보키에 포함되어 [1] 이 후보키가 되지 못합니다. 후보키의 부분집합이 아닐 경우에 해당 조합의 값들을 차례대로 list로 넣습니다. 이미 list에 같은 값이 있다는 것은 중복이 되는 값이 있으므로 유일하게 row를 구별할 수 없다는 뜻으로 후보키에 포함되지 않고, 모든 값이 다 list에 들어가게 되면 유일하게 row를 구별할 수 있으므로 해당 조합을 후보키에 넣으면 됩니다.

코드

https://github.com/kswim/Algorithm/blob/master/etc/42890.py