BOJ 3967 [매직 스타]

BOJ 매직 스타 : https://www.acmicpc.net/problem/3967

안녕하세요. 이번 문제는 백준 온라인 저지의 [매직 스타] 입니다.

순열 조합 문제인데요, 일반적으로 작성하면, 시간 초과를 부를 수 있습니다.

저는 백트레킹을 할 때, 현재 최소로 설정된 문자열보다 사전순으로 뒤에 있는 경우엔

끝까지 가지 않고 바로 back 했습니다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> x_index;    //x로 비어있는 인덱스 ([0] ~ [11])
vector<pair<int, int>> star_index;    //star를 형성하는 인덱스 (0,0 ~ 5,9)
char star[12];    //위에서부터 왼쪽 순으로.
char result[12];    //최소가 되는 문자열 결과 저장
bool ascii[12];    //해당 문자를 사용했는지?
string result_str;
string str;
bool is_26(char c1, char c2, char c3, char c4) {    //26이 되는지 체크
    return (int)c1-64 + (int)c2 - 64 + (int)c3 - 64 + (int)c4 - 64 == 26;
}
void DFS(int index, int size) {
    str = star;
    if(index != 0) {
        if(str.compare(result) > 0)    //사전순으로 앞서있지 않으면 back
            return;
    }
    if(size == x_index.size()) {    //모든 x를 채울 경우
        if(!is_26(star[0], star[2], star[5], star[7]))
            return;
        if(!is_26(star[0], star[3], star[6], star[10]))
            return;
        if(!is_26(star[1], star[2], star[3], star[4]))
            return;
        if(!is_26(star[1], star[5], star[8], star[11]))
           return;
        if(!is_26(star[4] ,star[6], star[9], star[11]))
            return;
        if(!is_26(star[7], star[8], star[9], star[10]))
            return;
        for(int i = 0; i <12; i++)
            result[i] = star[i];
        result_str = result;
        return;
    }
    for(int j = 0; j < 12; j++) {
        if(!ascii[j]) {    //해당 문자를 사용하지 않았으면
            ascii[j] = true;    //사용 후
            star[x_index[index]] = (char)(65 + j);    
            DFS(index + 1, size+1);
            ascii[j] = false;    //다시 풀기
        }
    }
}
int main() {
    char c;
    int index = 0;
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 9; j++) {
            cin >> c;
            if(c == '.') continue;
            star[index] = c;
            if(c == 'x') x_index.push_back(index);
            else ascii[(int)c-65] = true;
            result[index] = 'L';
            index++;
            star_index.push_back(make_pair(i, j));
        }
    }
    result_str = result;
    DFS(0, 0);
    index = 0;
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 9; j++) {
            if(!star_index.empty()) {
                if(star_index[0].first == i && star_index[0].second == j) {
                    cout << result[index++];
                    star_index.erase(star_index.begin());
                }
                else
                    cout <<".";
            }
            else
                cout<<".";
        }
        cout << endl;
    }
    return 0;
}