[BOJ/Silver 1] 백준 30090 백신 개발(C++)

문제 링크

https://www.acmicpc.net/problem/30090

30090번: 백신 개발

 

문제

평소 정보 보안에 관심이 많은 진흥이는 최근 들어 유행하고 있는 컴퓨터 바이러스에 대한 백신을 개발하려고 한다. 바이러스는 N개의 문자열로 이루어져 있다고 한다. 진흥이가 열심히 연구한 결과, 이 바이러스를 처치할 방법은 다음과 같다.

• 바이러스를 구성하는 N개의 문자열을 적당한 순서를 정하여 하나로 이어 붙여야 한다.
• 앞에 붙는 문자열의 마지막 k글자와 뒤에 붙는 문자열의 첫 k글자가 일치하도록 하는 1이상의 정수 k가 존재해야 한다. 조건을 만족하는 가장 큰 k에 대해서, 앞에 붙는 문자열의 마지막 k글자를 삭제하고, 뒤에 붙는 문자열을 그대로 붙인다.
•  N개의 문자열을 모두 이어 붙였을 때 가장 짧은 문자열이 백신이 된다.

진흥이를 도와 백신이 되는 문자열의 길이를 출력하자. 반드시 답이 존재하는 경우만 주어진다.

 

입력

첫 번째 줄에 바이러스를 구성하고 있는 문자열의 수 N(1 ≤ N ≤ 9)이 주어진다.

두 번째 줄부터 N개의 줄에 걸쳐서 바이러스를 구성하는 문자열이 주어진다. 이 때 문자열의 길이는 10이하이며, 영어 대문자로만 구성되어 있다.

 

출력

백신이 되는 문자열의 길이를 출력한다.

 

서브태스크

번호	배점	제한
1	7	N ≤ 2
2	23	N ≤ 5
3	19	모든 문자열이 A 또는 B 로만 구성 되어있다.
4	51	추가 제약 조건 없음

 

예제 입력 1

3
RUST
VIRUS
STAND

예제 출력 1

9

 

알고리즘 분류

• 백트래킹
• 문자열

 

풀이

N개의 문자열을 다 합쳐보는 경우의 수는 9!가지이므로 완전 탐색으로 백신을 찾을 수 있다.

문자열 A, B를 비교할 때, A의 뒤의 K자리의 문자열과 B의 앞의 K자리의 문자열이 같은지를 비교하고 같으면 서로 합친 새로운 문자열로 만든다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 10
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
vector<string> Vec;
bool Visited[MAX];
int Answer = INF;

void input() {
    cin >> N;
    Vec.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> Vec[i];
    }
}

string add_Strings(string A, string B) {
    string Result = A + B;
    int Len = min((int)A.length(), (int)B.length());
    for (int i = Len; i >= 1; i--) {
        string FrontA = A.substr(0, (int)A.length() - i);
        string PartA = A.substr((int)A.length() - i);
        string PartB = B.substr(0, i);
        string BackB = B.substr(i);
        if (PartA == PartB) {
            Result = FrontA + PartA + BackB;
            break;
        }
    }

    return Result;
}

void DFS(int Depth, string Vaccine) {
    if (Depth == N) {
        Answer = min(Answer, (int)Vaccine.length());
        return;
    }

    for (int i = 0; i < N; i++) {
        if (!Visited[i]) {
            Visited[i] = true;
            DFS(Depth + 1, add_Strings(Vaccine, Vec[i]));
            Visited[i] = false;
        }
    }
}

void settings() {
    DFS(0, "");
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}