BOJ(백준) 6300번 단어 퍼즐

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

6300번: 단어 퍼즐

구현 + 아호 코라식

 

아호 코라식 알고리즘에 대해서 알고 있어야 풀 수 있고 혹시 모른다면 kmp와 트라이를 먼저 배우는 것을 추천한다. 아호 코라식은 kmp와 트라이를 합친 알고리즘이기 때문이다

 

특별히 아호 코라식에 다른 알고리즘 추가됐거나 하지는 않지만 8가지 방향을 모두 확인해야 되고 그 위치와 방향의 종류까지 기록해야 되기 때문에 상당히 까다롭다.

 

코드가 너무 길고 복잡해지는 것을 방지하기 위해 dx와 dy 배열로 8가지 방향을, pdx오 pdy 배열로 탐색 위치를 옮기는 방향을, psx와 psy배열로 탐색의 시작점을 반복문으로 처리할 수 있게 했다.

 

check배열은 특정 방향에서는 쓸모 없는 탐색을 줄이기 위해 만들었다.

 

AC code

#include <bits/stdc++.h>
using namespace std;
vector<string> board,words;
vector<int> len;
vector<vector<vector<int>>> sol;
int L,C,W;
int dy[]={-1,-1,0,1,1,1,0,-1},dx[]={0,1,1,1,0,-1,-1,-1};
int check[][4]={{0,0,1,0},{0,0,1,1},{0,0,0,1},{1,0,0,1},{1,0,0,0},{1,1,0,0},{0,1,0,0},{0,1,1,0}};
int pdx[]={1,0,1,0};
int pdy[]={0,1,0,1};
int psx[]={0,1,0,0};
int psy[]={0,0,1,0};

bool isOk(int yy,int xx) {
	if(yy>=0&&yy<L&&xx>=0&&xx<C) return true;
	else return false;
}

struct trie
{
    bool isFinish;
    unordered_map<char,trie*> next;
    vector<char> v;
    trie* fail;
    int word;
    
	trie() {
		fail=nullptr;
		isFinish=false;
	}
	
	~trie() {
		for(auto i:v) delete(next[i]);
	}
	
	void insert(string &str,int idx,int num) {
	    if(str[idx]=='\0') {
	    	word=num;
	        isFinish=1;
	        return;
	    } 
	    if(next[str[idx]]==nullptr) {
	        next[str[idx]]=new trie;
	        v.push_back(str[idx]);
	    }
	    next[str[idx]]->insert(str,idx+1,num);
	}
	
	void init() {
	    queue<trie*> q;
	    q.push(this);
	    while(!q.empty())
	    {
	        trie* cur=q.front();
	        q.pop();
	        for(auto i:cur->v) {
	            trie* next=cur->next[i];
	            if(cur==this) next->fail=this;
	            else {
	                trie* failure=cur->fail;
	                while(failure!=this&&failure->next[i]==nullptr)failure=failure->fail;
	                if(failure->next[i]!=nullptr)failure=failure->next[i];
	                next->fail=failure; 
	            }
	            if(next->fail->isFinish) {
	            	next->isFinish=true; 
	            	next->word=next->fail->word;
				}  
	            q.push(next);
	        }
	    }
	}
	
	void kmp() {
	    for(int i=0;i<8;i++) {
	    	for(int k=0;k<4;k++) {
	    		int sy=0,sx=0;
	    		if(psy[k])sy=L-1;
	    		if(psx[k])sx=C-1;
	    		if(check[i][k]) for(;isOk(sy,sx);sx+=pdx[k],sy+=pdy[k]) {
		    		trie* cur=this;
		    		for(int cy=sy,cx=sx;isOk(cy,cx);cy+=dy[i],cx+=dx[i]) {
		    			char now=board[cy][cx];
		    			while(cur!=this&&cur->next[now]==nullptr) cur=cur->fail;
				        if(cur->next[now]!=nullptr) cur=cur->next[now];
				        if(cur->isFinish) {
				        	sol[cur->word].push_back({cy-dy[i]*(len[cur->word]-1),cx-dx[i]*(len[cur->word]-1),i});
						}
					}
				}
			}
		}
	}
	
};

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);
    cin>>L>>C>>W;
    trie* myTrie=new trie;
    board=vector<string>(L);
    words=vector<string>(W);
    len=vector<int>(W);
    sol=vector<vector<vector<int>>>(W);
    for(int i=0;i<L;i++) cin>>board[i];
	for(int i=0;i<W;i++) {
    	cin>>words[i];
    	len[i]=words[i].length();
    	myTrie->insert(words[i],0,i);
	}
	myTrie->init();
	myTrie->kmp();
	for(auto i:sol) {
		vector<int> v(3,1001);
		for(auto k:i) {
			if(v[0]>k[0]) v=k;
			else if(v[0]==k[0]&&v[1]>k[1]) v=k;
			else if(v[1]==k[1]&&v[2]>k[2]) v=k;
		}
		cout<<v[0]<<" "<<v[1]<<" "<<(char)((int)'A'+v[2])<<"\n";
	}
}

 

 

오랜만에 풀어본 복잡한 구현 문제라 그런지  꽤 재미있게 풀었다