[BaekJoon/백준] 3967번 매직 스타

 

이전에 못 풀었던 문제를 다시 보았다.

 

12의 숫자를 뽑아서 각 규칙의 합이 모두 26이 되어야 하는 문제인데

 

12개를 모두 뽑은 뒤에 평가하게 될 경우, 12!로 시간초과가 난다.

 

그렇기 때문에, 평가할 수 있을 때 마다 평가를 조기로 해줘야 한다.

EVALUATE 함수 내의 if문의 순서가 그러하다

#include <iostream>

using namespace std;


char MAP[5][9];
bool CHECK[12];
int CT;

void EVALUATE() {
    
    // 채워져서 평가 가능한 순서대로
    if((MAP[1][1] - 'A' + 1) + (MAP[1][3] - 'A' + 1) + (MAP[1][5] - 'A' + 1) + (MAP[1][7] - 'A' + 1) != 26)
        return;
    
    if((MAP[0][4] - 'A' + 1) + (MAP[1][3] - 'A' + 1) + (MAP[2][2] - 'A' + 1) + (MAP[3][1] - 'A' + 1) != 26)
        return;

    if((MAP[0][4] - 'A' + 1) + (MAP[1][5] - 'A' + 1) + (MAP[2][6] - 'A' + 1) + (MAP[3][7] - 'A' + 1) != 26)
        return;
    
    if((MAP[3][1] - 'A' + 1) + (MAP[3][3] - 'A' + 1) + (MAP[3][5] - 'A' + 1) + (MAP[3][7] - 'A' + 1) != 26)
        return;

    if((MAP[1][1] - 'A' + 1) + (MAP[2][2] - 'A' + 1) + (MAP[3][3] - 'A' + 1) + (MAP[4][4] - 'A' + 1) != 26)
        return;

    if((MAP[1][7] - 'A' + 1) + (MAP[2][6] - 'A' + 1) + (MAP[3][5] - 'A' + 1) + (MAP[4][4] - 'A' + 1) != 26)
        return;

    
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 9; j++) {
            cout << MAP[i][j];
        }
        cout << "\n";
    }

    exit(0);
    
}


void dfs(int start) {
    

    EVALUATE();
    
    
    int k, x, y;
    // 'x' 위치 찾기
    for(k = start; k < 45; k++) {
        
        x = k / 9;
        y = k % 9;
        
        if(MAP[x][y] == 'x')
            break;
    }
    
    
    for(int i = 0; i < 12; i++) {
        
        if(!CHECK[i]) {
            
            MAP[x][y] = 'A' + i;
            CHECK[i] = true;
            
            dfs(k + 1);
            
            MAP[x][y] = 'x';
            CHECK[i] = false;

            
            
        }
        
    }
    
}

int main() {
    
    
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 9; j++) {
            cin >> MAP[i][j];
            
            if(MAP[i][j] != 'x' && MAP[i][j] != '.') {
                CHECK[MAP[i][j] -'A'] = true;
                CT++;
            }
            
        }
    }
    
    dfs(0);
    
}

 

블로그는 아래 블로그를 참고하면 이해가 쉬울 것 같다.

https://hyonee.tistory.com/70

 

 

소요 시간 : 2시간