백준 18216번 Ambiguous Encoding

문제 요약

0과 1로 이루어진 문자열 $n$개가 주어진다. 이런 문자열들 중에서 적당히 골라서 이어 붙인 문자열을 $s$라고 하자. 이 때, 주어진 문자열 $n$개를 이용해서 $s$를 분할하는 방법이 두 가지 이상이라면 $s$를 ambiguous하다고 한다.

만들 수 있는 ambiguous한 문자열 중에서 가장 길이가 짧은 것의 길이를 출력하시오. 만약 만들 수 없다면 0을 출력하시오.

주어지는 $n$개의 문자열의 길이는 16 이하이다. $ 1 \le n \le 1000 $

풀이

예제를 살펴보자. 주어진 문자열이 0, 01, 10인데 010은 0, 10 혹은 01, 0으로 분할될 수 있다. 따라서 010은 ambiguous한 문자열이고 이게 제일 짧은 경우이다.

ambiguous한 문자열이 되기 위해서는 어떤 문자열 $s$가 $t$의 prefix여야만 한다. 만약 prefix가 아니라면 구분이 잘 될 것이다.

$t$가 $s$의 prefix 중 하나라고 하자. 그러면 $s-t$에 해당하는 문자열을 만들 수 있다면 $s$는 amiguous한 문자열이 될 것이다.

$s-t$에 해당하는 문자열을 갖고 있다면 바로 만들면 되지만 만약 그런 문자열이 없다면 어떻게 할까?

다시 $s-t$의 prefix를 찾아와서 $t$의 뒤에 붙여서 $t'$를 만들고 $s-t'$를 만들 수 있는지 확인해야 할 것이다.

혹은 $s-t$를 prefix로 가지는 문자열 $s'$를 가지고 와서 $t$ 뒤에 붙이고, $s'-s$를 만들 수 있는지 확인해야 할 것이다.

이러한 과정 중에서 어떤 문자열을 붙이고 추가로 만들어야 되는 부분을 suffix라고 하자. 이러한 suffix가 될 수 있는 종류의 수는 최대 $2^{16}$개 밖에 없다.

그리고 그러한 suffix를 완성시키려면 필요한 과정은 어느 상황에서건 동일할 것이다. DP를 하자.

우리가 구할 DP를 이렇게 정의하자.
$$
dp(s) = \text{만들여야 할 suffix가 s인 prefix 중에서 가장 길이가 작은 prefix의 길이}
$$
만약 $s$가 우리가 가지고 있는 문자열 중에 하나 였다면 prefix + s로 ambiguous한 문자열이 만들어진다.

그리고 해당 문자열의 길이는 $dp(s) + s.size()$가 될 것이다.

이거로 dp값을 구하면 답이 나온다. 구할 때는 다익스트라를 사용해야 한다.

#include<bits/stdc++.h>
using namespace std;
map<string, int> dp;
int N;
set<string> ss;
string a[1005];

// is b prefix of a?
bool prefix(string &a, string &b) {
   if(a.size() < b.size()) return false;
   for(int i=0;i<b.size();++i) if(a[i] != b[i]) return false;
   return true;
}

int main() {
   cin.tie(nullptr); ios::sync_with_stdio(false);
   cin >> N;
   for(int i=0;i<N;++i) {
      cin >> a[i];
      ss.insert(a[i]);
   }
   priority_queue<pair<int, string>, vector<pair<int,string>>, greater<>> pq;
   for(int i=0;i<N;++i) {
      for(int j=0;j<N;++j) {
         if(i == j) continue;
         if(!prefix(a[i], a[j])) continue;
         // a[j] is prefix of a[i]
         string suffix = a[i].substr(a[j].size());
         dp[suffix] = a[j].size();
         pq.push(make_pair(a[j].size(), suffix));
      }
   }
   int ans = 1e9;
   while(!pq.empty()) {
      auto p = pq.top();
      int d = p.first;
      string cur = p.second;
      int cache = dp[cur];
      pq.pop();
      if(cache < d) continue;
      if(cache + cur.size() >= ans) continue;
      if(ss.find(cur) != ss.end()) {
         ans = min(ans, d + (int)cur.size());
         continue;
      }
      for(int i=0;i<N;++i) {
         if(cur.size() == a[i].size()) continue;
         if(a[i].size() < cur.size()) {
            if(!prefix(cur, a[i])) continue;
            string suffix = cur.substr(a[i].size());
            int dist = d + a[i].size();
            if(dp.find(suffix) == dp.end() || dp[suffix] > dist) {
               dp[suffix] = dist;
               pq.push(make_pair(dist, suffix));
            }
         }
         else {
            if(!prefix(a[i], cur)) continue;
            string suffix = a[i].substr(cur.size());
            int dist = d + cur.size();
            if(dp.find(suffix) == dp.end() || dp[suffix] > dist) {
               dp[suffix] = dist;
               pq.push(make_pair(dist, suffix));
            }
         }
      }
   }
   if(ans == 1e9) cout << 0 << '\n';
   else cout << ans << '\n';
   return 0;
}