[ 백준 BOJ ] 20166번 - 문자열 지옥에 빠진 호석(C++)

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

 

생각 흐름

• bfs를 돌면서 이동할 때마다 만들어진 문자열에 대해 cnt 배열에 갯수를 카운팅 해주었다. (최대 5번 이동)
• cnt 배열은 최대 문자열의 길이가 5인 것을 감안하여 cnt[27][27][27][27][27]와 같이 만들었다. 
  • unordered_map을 사용하려고 했는데 26^5가 천만을 넘어가서 시간초과가 날 거 같아서 안 했다.
• 즉, 만약 a 위치에서부터 시작해서 b, c, d, e 순으로 이동한다면 아래와 같이 cnt의 개수를 세주었다.
  1. cnt['a'-'a'+1][0][0][0][0]++
  2. cnt['a'-'a'+1]['b'-'a'+1][0][0][0]++
  3. cnt['a'-'a'+1]['b'-'a'+1]['c'-'a'+1][0][0]++
  4. cnt['a'-'a'+1]['b'-'a'+1]['c'-'a'+1]['d'-'a'+1][0]++
  5. cnt['a'-'a'+1]['b'-'a'+1]['c'-'a'+1]['d'-'a'+1]['e'-'a'+1]++
• 이를 모든 격자 위치에서 진행해주면 된다. 예를 들어 N=3, M=4 일때 (0,0), (0,1), ..., (2,2), (2,3)와 같이 모든 위치에 대해 bfs를 돌면 된다.

다른 풀이를 봤는데, unordered_map을 사용한 코드를 보았다.
map에 신이 좋아하는 문자열에 대해 0으로 초기화 시켜놓고, bfs를 돌면서 해당 문자열이 map 안에 존재하는지 검증 후 카운팅해주는 로직이었다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M, K;
vector<string> v;

int mx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int my[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int cnt[27][27][27][27][27];
vector<string> question;

void increase(string word){
    int tmp[5];
    for(int i = 0; i<5; i++){
        tmp[i]=0;
    }
    
    for(int i = 0; i<word.size(); i++){
        tmp[i]=word[i]-'a'+1;
    }
    
    cnt[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]]++;
}

void bfs(int h, int w){
    queue<pair<string,pair<int, int>>> q;
    string tmp = "";
    q.push({tmp+v[h][w],{h,w}});
    
    while(!q.empty()){
        string word = q.front().first;
        int y = q.front().second.first;
        int x = q.front().second.second;
        q.pop();
        
        increase(word);
        
        if(word.size()==5) continue;
        
        for(int i = 0; i<8; i++){
            int dx = x+mx[i];
            int dy = y+my[i];
            
            dx = dx==-1?M-1:dx;
            dx = dx==M?0:dx;
            dy = dy==-1?N-1:dy;
            dy = dy==N?0:dy;
            
            q.push({word+v[dy][dx],{dy,dx}});
        }
    }
}

int ans(string word){
    int tmp[5];
    for(int i = 0; i<5; i++){
        tmp[i]=0;
    }
    
    for(int i = 0; i<word.size(); i++){
        tmp[i]=word[i]-'a'+1;
    }
    
    return cnt[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N>>M>>K;
    for(int i = 0; i<N; i++){
        string tmp;
        cin>>tmp;
        
        v.push_back(tmp);
    }
    
    for(int i = 0; i<K; i++){
        string tmp;
        cin>>tmp;
        
        question.push_back(tmp);
    }
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            bfs(i,j);
        }
    }
    
    for(auto s : question){
        cout<<ans(s)<<endl;
    }
    
    return 0;
}