[BOJ/Platinum 1] 백준 10538 빅 픽쳐(C++)

문제 링크

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

10538번: 빅 픽쳐

 

 

문제

재혁이는 화가인데 거지다. 그래서 새 그림을 그릴 화판조차도 없다. 그러나 재혁이는 방금 유레카를 외쳤다. "아직 팔리지 않은 그림들을 꿰매 이어붙여서 새로운 큰 그림을 만들면 화판도 필요없고 새 그림도 만들고 개이득이다. 이거 완전 빅 픽쳐 아님?" 꼬박 하루의 노동을 거쳐, 재혁이는 큰 그림 걸작 하나를 만들어내고야 말았다.

그러던 어느 날, 재혁이는 예상치 못한 전화를 받고 말았다. 전화의 내용은 아직 팔리지 않았던 그림 중 하나를 사겠다는 것이었다. 그런데 재혁이는 큰 그림을 만드는 데 어떤 그림들을 사용했는지 기록하는 것을 까먹었다. 그래서 자기 걸작의 어느 곳에 그 그림이 사용되었는지를 찾아야 한다.

흑백으로 표현된 그림과 그걸 사용해 만든 걸작이 주어졌을 때, 재혁이가 그림을 찾는 것을 도울 수 있는가? 

입력

첫 번째 줄에 4개의 정수 hp wp hm wm가 주어진다. 각각 사용한 그림의 높이와 너비, 걸작의 높이와 너비를 의미한다. 이어서 hp개의 줄에 걸쳐 사용한 그림이 주어지고, hm개의 줄에 걸쳐 걸작이 주어진다. 그림은 'x' 또는 'o'만으로 이루어져 있다.

각 그림의 너비와 높이는 1 이상 2000 이하이며, 걸작의 넓이와 높이는 각각 사용한 그림의 너비와 높이보다 크거나 같다.

출력

사용한 그림이 걸작에서 있을 수 있는 위치의 개수를 출력한다.

예제 입력 1

4 4 10 10
oxxo
xoox
xoox
oxxo
xxxxxxoxxo
oxxoooxoox
xooxxxxoox
xooxxxoxxo
oxxoxxxxxx
ooooxxxxxx
xxxoxxoxxo
oooxooxoox
oooxooxoox
xxxoxxoxxo

예제 출력 1

4

힌트

알고리즘 분류

• 자료 구조
• 트라이
• kmp

풀이

우선 팔아야 할 그림을 트라이에 저장해야 한다. 그러기 위해서는 먼저 HP개의 줄로 이루어진 그림의 각각의 줄을 해싱을 통해 번호를 매겨야 한다.

이후 그림의 각각의 줄에 해당하는 패턴을 트라이에 insert하고, 패턴의 끝에는 해당 패턴의 번호를 기록해둔다.

이제 팔아야 할 그림의 패턴이 걸작에 몇 번 나타나는지를 찾아야 한다. 이것은 kmp 알고리즘을 활용하여 찾는다.

걸작의 각각의 줄의 현재 칸까지 보았을 때 몇 번째 패턴이 나타나는지를 기록한다. 이렇게 하면 걸작의 특정 부분에 팔아야 할 그림이 존재하는지를 그림의 각각의 줄에 나타나는 패턴의 번호를 확인하는 것으로 쉽게 알 수 있다.

이제 마지막으로 걸작에 나타난 팔아야 할 그림의 개수를 구한다. 이것 역시 kmp를 활용한다. 먼저 팔아야 할 그림의 첫 번째 줄부터 마지막 줄까지의 패턴의 번호들을 트라이에 insert하고, 번호의 끝에는 해당 노드의 end_Point를 1로 초기화함으로써 그림의 마지막 줄이라고 기록한다.

그리고 걸작의 각각의 열의 HP개의 칸을 보았을 때 팔아야 할 그림의 패턴의 번호와 일치하는지 체크하는데, 현재 노드까지 왔을 때 end_Point가 1이라면 그림의 처음부터 마지막 줄까지 패턴 번호가 전부 일치했다는 뜻이므로 팔아야 할 그림을 찾은 것이다.

이런 식으로 팔아야 할 그림의 개수를 구하고 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define MAX 2001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int HP, WP, HM, WM;
string S;
unordered_map<string, int> UM;
vector<string> Picture, Masterpiece;
int Visited[MAX][MAX];

struct TRIE {
    int end_Index;
    vector<pair<int, TRIE*> > Child;
    TRIE* Fail;

    TRIE() {
        end_Index = 0;
        Child.clear();
        Fail = nullptr;
    }

    void insert_Pattern(string Pattern, int Index) {
        TRIE* NowTrie = this;

        for (int i = 0; i < Pattern.size(); i++) {
            int Now = Pattern[i] - 'a';

            bool Flag = false;
            for (auto IT : NowTrie->Child) {
                if (IT.first == Now) {
                    Flag = true;
                    NowTrie = IT.second;
                    break;
                }
            }
            if (!Flag) {
                NowTrie->Child.push_back(make_pair(Now, new TRIE));
                NowTrie = NowTrie->Child.back().second;
            }
        }
        NowTrie->end_Index = Index;
    }

    void insert_Hash() {
        TRIE* NowTrie = this;

        for (int i = 0; i < Picture.size(); i++) {
            int Now = UM[Picture[i]];

            bool Flag = false;
            for (auto IT : NowTrie->Child) {
                if (IT.first == Now) {
                    Flag = true;
                    NowTrie = IT.second;
                    break;
                }
            }
            if (!Flag) {
                NowTrie->Child.push_back(make_pair(Now, new TRIE));
                NowTrie = NowTrie->Child.back().second;
            }
        }
        NowTrie->end_Index = 1;
    }

    void find_Fail() {
        TRIE* RootTrie = this;
        queue<TRIE*> Q;
        Q.push(RootTrie);

        while (!Q.empty()) {
            TRIE* NowTrie = Q.front();
            Q.pop();

            for (auto& IT : NowTrie->Child) {
                TRIE* NextTrie = IT.second;

                if (NowTrie == RootTrie) {
                    NextTrie->Fail = RootTrie;
                }
                else {
                    TRIE* PrevTrie = NowTrie->Fail;

                    while (PrevTrie != RootTrie) {
                        bool Flag = false;
                        for (auto A : PrevTrie->Child) {
                            if (A.first == IT.first) {
                                Flag = true;
                                break;
                            }
                        }
                        if (Flag) {
                            break;
                        }
                        PrevTrie = PrevTrie->Fail;
                    };
                    for (auto A : PrevTrie->Child) {
                        if (A.first == IT.first) {
                            PrevTrie = A.second;
                            break;
                        }
                    }
                    NextTrie->Fail = PrevTrie;
                }
                if (NextTrie->Fail->end_Index > 0) {
                    if (NextTrie->end_Index == 0) {
                        NextTrie->end_Index = NextTrie->Fail->end_Index;
                    }
                }
                Q.push(NextTrie);
            }
        };
    }
};

int kmp(TRIE* Root) {
    int Answer = 0;

    for (int i = 0; i < HM; i++) {
        TRIE* NowTrie = Root;
        for (int j = 0; j < WM; j++) {
            int Now = Masterpiece[i][j] - 'a';

            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            Visited[i][j] = NowTrie->end_Index;
        }
    }

    TRIE* NewRoot = new TRIE();
    NewRoot->insert_Hash();
    NewRoot->find_Fail();

    for (int i = 0; i < WM; i++) {
        TRIE* NowTrie = NewRoot;
        for (int j = 0; j < HM; j++) {
            int Now = Visited[j][i];

            while (NowTrie != NewRoot) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->end_Index == 1) {
                Answer++;
            }
        }
    }

    return Answer;
}

void input() {
    TRIE* Root = new TRIE();
    cin >> HP >> WP >> HM >> WM;
    for (int i = 0; i < HP; i++) {
        cin >> S;
        Picture.push_back(S);
        if (UM.find(S) == UM.end()) {
            UM.insert(make_pair(S, i + 1));
        }
        Root->insert_Pattern(S, UM[S]);
    }
    Root->find_Fail();
    for (int i = 0; i < HM; i++) {
        cin >> S;
        Masterpiece.push_back(S);
    }
    cout << kmp(Root) << "\n";
    delete Root;
}

int main() {
    FASTIO
    input();

    return 0;
}