문제 소개
비밀번호로 보호되는 금고가 하나 있다고 가정해 보겠습니다. 비밀번호는 n자리 숫자로 이루어져 있으며, 각 자리에는 0부터 k-1까지의 숫자 중 하나가 들어갈 수 있습니다. 흥미로운 점은 금고에 숫자를 계속 입력하면, 마지막으로 입력된 n자리가 자동으로 실제 비밀번호와 대조된다는 것입니다.
예를 들어 올바른 비밀번호가 "563"이라면, 우리가 "285639"를 입력했을 때 입력값의 접미사(suffix)인 "563"이 실제 비밀번호와 일치하므로 금고는 열리게 됩니다.
따라서 우리의 목표는 입력 과정 중 어느 시점에서든 반드시 금고를 열 수 있음을 보장하는 최소 길이의 문자열을 찾는 것입니다.
n = 2, k = 2가 입력으로 주어진다면, 결과는 "01100", "00110", "10011", "11001" 중 무엇이든 될 수 있습니다.
접근 방법: DFS 탐색
이 문제의 핵심은 모든 가능한 n자리 조합을 겹치는 방식으로 단 한 번씩만 포함하는 문자열을 만드는 것입니다. 이는 그래프 이론에서 유명한 De Bruijn 수열을 구성하는 과정과 본질적으로 같으며, 깊이 우선 탐색(DFS)으로 해결할 수 있습니다.
풀이 절차는 다음과 같습니다.
- 이미 방문한 문자열을 저장하기 위한 집합(set)
visited를 정의합니다. - 문자열 s와 k를 인자로 받는 함수
dfs()를 정의합니다. - i를 0부터 k-1까지 증가시키며 다음을 반복합니다.
temp := s + i(문자열)로 새 문자열을 만듭니다.- temp가 visited에 없다면:
- temp를 visited에 삽입합니다.
- temp에서 첫 번째 문자를 제거한 부분 문자열로 갱신합니다.
dfs(temp, k)를 재귀 호출합니다.ret := ret + i(문자열)로 결과에 숫자를 추가합니다.
- 메인 메서드에서는 다음을 수행합니다.
- n == 1이고 k == 1이면 "0"을 바로 반환합니다.
- ret과 s를 빈 문자열로 초기화합니다.
- s에 "0"을 n-1번 이어 붙여 시작 노드를 만듭니다.
dfs(s, k)를 호출합니다.- 마지막으로 ret 뒤에 "0"을 n-1번 이어 붙인 후 반환합니다.
DFS가 재귀적으로 돌아오면서 숫자를 역순으로 기록하기 때문에, 마지막에 시작 노드였던 "0"들을 n-1개 덧붙여야 완전한 답이 된다는 점이 이 풀이의 핵심 포인트입니다.
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
set <string> visited;
string ret;
string crackSafe(int n, int k) {
if(n == 1 && k == 1) return "0";
ret = "";
string s = "";
for(int i = 0; i < n - 1; i++){
s += "0";
}
dfs(s, k);
for(int i = 0; i < n - 1; i++) ret += "0";
return ret;
}
void dfs(string s, int k) {
string temp;
for(int i = 0; i < k; i++){
temp = s + to_string(i);
if(!visited.count(temp)){
visited.insert(temp);
temp = temp.substr(1);
dfs(temp, k);
ret += to_string(i);
}
}
}
};
main(){
Solution ob;
cout << (ob.crackSafe(2,2));
}입력
2 2
출력
01100
마무리
이 알고리즘은 각 상태(길이 n의 문자열)를 노드로, 한 글자 추가 동작을 간선으로 보는 오일러 경로(Eulerian Path) 관점에서 이해하면 명확해집니다. DFS가 모든 간선을 정확히 한 번씩 사용하도록 경로를 구성하고, 재귀 종료 시점에 숫자를 기록한 뒤 앞뒤를 적절히 이어 붙이면, 모든 비밀번호 조합을 포함하는 최소 길이 문자열을 얻을 수 있습니다. 시간 복잡도는 생성해야 하는 총 문자열 개수에 비례하여 O(k^n × n) 수준으로 효율적입니다.