[C++ 백준 풀이] 7575번 : 바이러스 / 10266번 : 시계 사진들 (KMP 응용)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 7575번 : '바이러스', 10266번 : '시계 사진들' 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum V에 해당하며, 문제를 풀이하기 위해 KMP 알고리즘에 대한 이해가 필요합니다.

 

[C++ 알고리즘] KMP 알고리즘 (O(N+M) 문자열 탐색 알고리즘)

KMP 알고리즘에 대한 원리와 코드 설명은 위의 링크에 정리되어 있으며, 여기에서는 간단한 풀이에 대한 아이디어만 정리하겠습니다.

 

 

7575번 : 바이러스

 

이 문제는 출처를 알아보니 정보올림피아드 2013 지역본선 중등부, 고등부 5번 문제였습니다.

저는 문제 태그가 KMP로 되어있어 바로 KMP 알고리즘은 사용해서 풀었지만, 만약 그냥 문제를 주었다면 KMP를 사용하는 문제라는 것을 생각하는데 시간이 조금 걸렸을 것 같습니다.

 

 

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 105
using namespace std;

int N, K, L, Value, Yes = 0;
vector<int> Code[MAX];

vector<int> Fail(vector<int> &SubCode) {
    vector<int> Pi(SubCode.size());
    for(int i=1, j=0; i<SubCode.size(); i++) {
        while(j>0 && SubCode[i] != SubCode[j]) j = Pi[j-1];
        if(SubCode[i] == SubCode[j]) Pi[i] = ++j;
    }
    return Pi;
}

int KMP(vector<int> &Code, vector<int> &SubCode) {
    vector<int> Pi = Fail(SubCode);
    for(int i=0, j=0; i<Code.size(); i++) {
        while(j>0 && Code[i] != SubCode[j]) j = Pi[j-1];
        if(Code[i] == SubCode[j]) {
            if(j == SubCode.size()-1) return 1;
            else j++;
        }
    }
    return 0;
}

int main() {
    scanf("%d %d", &N, &K);
    for(int i=0; i<N; i++) {
        scanf("%d", &L);
        for(int j=0; j<L; j++) {
            scanf("%d", &Value);
            Code[i].push_back(Value);
        }
    }
    for(int i=0; i<Code[0].size()-K+1; i++) {
        vector<int> SubCode(K);
        for(int j=0; j<K; j++) SubCode[j] = Code[0][i+j];
        int Check = 1;
        for(int j=1; j<N; j++) {
            vector<int> RevCode = Code[j];
            reverse(RevCode.begin(), RevCode.end());
            if(!KMP(Code[j], SubCode) && !KMP(RevCode, SubCode)) Check = 0;
        }
        if(Check) Yes = 1;
    }
    if(Yes) printf("YES");
    else printf("NO");
}

 

전체적인 탐색 시간에 대해 생각해보면, N은 100 이하, K는 1000 이하이므로 첫 번째 코드를 기준으로 잡아서 나올 수 있는 모든 SubCode에 대해 각각 탐색을 해도 시간이 충분함을 알 수 있습니다.

따라서 우선은 Code 벡터에 모든 코드를 저장해주고, 길이 K의 SubCode를 추출해줍니다. (SubCode = Code[0][i+j] 부분)

그 다음 Reversed Code를 하나 따로 선언해서 Code[j]를 뒤집은 배열을 저장해줍니다.

이제 KMP 알고리즘을 구현하여 여기에 Code[j]와 뒤집힌 Code[j]에 대해 각각 SubCode가 포함되는지를 검사해주면 됩니다.

모든 코드에 대해 검사하여 하나라도 포함되지 않는다면 일단 이 SubCode에 대해서는 바이러스에 해당하는 코드가 없다는 뜻이므로 Check = 0으로 만들어줍니다.

만약 모든 코드가 SubCode를 포함한다면 Check = 1로 만들어주고, 발견되었으므로 YES를 출력해주면 됩니다.

 

 

 

정답 인증 및 채점 결과는 위와 같습니다.

 

 

10266번 : 시계 사진들

 

0~360000 사이의 각도를 가지고 있는 N개의 침들에 대해서, 두 세트의 입력이 주어지면 이들이 돌려서 같은 모양이 되는지의 여부를 출력하는 문제입니다.

처음 보았을 때는 이 문제가 KMP 알고리즘을 사용해서 푸는 것임을 깨닫기 힘들고, 문제 분류가 KMP로 되어있는 것을 본다고 하더라도 어떻게 응용해야할지 방향이 잘 잡히지 않습니다.

이 문제를 KMP 알고리즘을 응용하여 풀이하는 아이디어를 설명해보겠습니다.

 

 

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

vector<int> Fail(string Pattern) {
    vector<int> Pi(Pattern.length());
    for(int i=1, j=0; i<Pattern.length(); i++) {
        while(j>0 && Pattern[i] != Pattern[j]) j = Pi[j-1];
        if(Pattern[i] == Pattern[j]) Pi[i] = ++j;
    }
    return Pi;
}

bool KMP(string Str, string Pattern) {
    vector<int> Pi = Fail(Pattern), Pos;
    for(int i=0, j=0; i<Str.length(); i++) {
        while(j>0 && Str[i] != Pattern[j]) j = Pi[j-1];
        if(Str[i] == Pattern[j]) {
            if(j == Pattern.length()-1) return true;
            else j++;
        }
    }
    return false;
}

int main() {
    int N, Value;
    scanf("%d", &N);
    string A, B;
    for(int i=0; i<360000; i++) A += '0', B += '0';
    for(int i=0; i<N; i++) {
        scanf("%d", &Value);
        A[Value] = '1';
    }
    for(int i=0; i<N; i++) {
        scanf("%d", &Value);
        B[Value] = '1';
    }
    if(KMP(A+A, B)) printf("possible");
    else printf("impossible");
}

 

 

풀이는 위와 같은데, 각도로 가질 수 있는 값들의 범위는 36만으로 고정이므로 36만 길이의 문자열에서 각도 i를 침이 나타내고 있으면 1으로, 아니라면 0으로 구성한 뒤 이들을 비교해주는 것입니다.

위의 코드에서는 A와 B 두 개의 문자열이 있을 때 A를 두 번 이어붙이고 B가 A의 부분 문자열인지를 확인함으로써 시계를 돌려서 겹치는지를 확인할 수 있습니다.

 

 

 

위와 같이 정답을 확인할 수 있습니다.