8905: 리트

• toc {:toc}

문제 확인하기

풀이

백트래킹 문제를 많이 안 풀어봐서 구조가 익숙하지 않았다. 추후에 다시 풀어봐야겠다.

• 전체적인 구조는 원래 문장과 리트 문장을 하나하나 전부 연결시켜보는 방식이다.
• 연결시키는 과정에서 올바른 연결이 아니라면 되돌아오는 백트래킹 방식을 사용한다.
• 올바른 연결이 아닌 경우는 리트 연결을 한 알파벳이 다시 나타났을 때 연결된 리트 표현과 알파벳이 가리키는 리트 표현이 동일한지 여부이다. ex)aa → @@ 인 경우 올바른 표현, aa → @! 인 경우 올바르지 않은 연결
• o_idx와 l_idx가 동시에 끝에 도달한다면 모두 연결된 상태이므로 true 반환
• 둘 중 하나만 끝에 도달하면 연결이 올바르지 않은 상태이므로 false 반환

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
 
int k;
string original, leet_word;
string leet_mapping[30];
 
bool isPossible(int o_idx, int l_idx){
    if(o_idx == original.length() && l_idx == leet_word.length()){
        return true;
    }
    if(o_idx == original.length() || l_idx == leet_word.length()){
        return false;
    }
    int alpha_idx = original[o_idx]-'a';
    if(leet_mapping[alpha_idx] == ""){  // 리트 표현이 연결되지 않은 경우
        for(int i = 1; i <= k && l_idx + i <= leet_word.length(); i++){
            leet_mapping[alpha_idx] = leet_word.substr(l_idx, i);
            if(isPossible(o_idx+1, l_idx+i)){
                return true;
            }
        }
		leet_mapping[alpha_idx] = "";  // 되돌아 오는 과정에서 초기화
    }
    else{                              // 리트 표현이 연결되어 있는 경우
        string mapped_leet = leet_mapping[alpha_idx];
        if(mapped_leet == leet_word.substr(l_idx, mapped_leet.length())){
            if(isPossible(o_idx+1, l_idx+mapped_leet.length())){
                return true;
            }
        }
    }
    return false;
}
 
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
 
    int T;
    cin >> T;
    while(T--){
        fill(leet_mapping, leet_mapping+30, "");
        cin >> k >> original >> leet_word;
        bool res = isPossible(0, 0);
        if(res) cout << 1 << endl; 
        else cout << 0 << endl;
    }
 
    return 0;
}