[BaekJoon/백준] 1941번 소문난 칠공주

 

이거 이틀이나 썼다.

 

원래 어제 풀었어야 했는데, 어제 두시간을 붙잡아도 풀지 못해서

오늘 다시 첨부터 짰다. 오늘도 오래 걸렸다.

 

 

짚고 넘어가야 할 하나가 있다.

 

이 문제에선 DFS(or BackTracking)이 두 종류가 사용되었다. 말 그대로 필요에 의해 두 가지로 활용되었다.

 

 

1. Arr[5][5] 행렬에서 7개를 뽑는 모든 경우의 수를 위한 DFS

5 x 5 행렬이 있을 때, 각 한번씩만 탐색해보는 경우의 수가 아니라, 7개를 뽑는 경우의 수. 조합이다.

매번 true / false를 토글해 가면서 뽑는다.
25개 중에서 7개를 뽑는 경우의 수.  대략 O(25C7)이 되겠다.

visit[check] = true;
DFS(i + 1)
visit[check] = false;

 

2. Arr[5][5] 행렬에서, 한 번씩 탐색해보는 완전 탐색 DFS

일단 뽑은 뒤에, 각각이 인접했는지를 확인할 때 사용된다. 대략 O(25)가 되겠다.

위 처럼 토글이 필요 없다. 그냥 한번 true 한 거 그대로 유지하며 나머지를 탐색한다.

 

 

---

 

 

#include <iostream>
#include <cstring>

using namespace std;


// 전체 맵
string MAP[5];

// 하 상 좌 우
int mx[4] = {1, -1, 0, 0};
int my[4] = {0, 0, -1, 1};


bool SELECT_CHECK[5][5]; // 뽑은 위치들을 나타내는 배열


bool ADJACENT_CHECK[5][5]; // 인접인지 체크할 때 사용하는 배열
int ADJACENT_COUNT; // 인접 체크가 7개가 되면 모두 체크한 것이므로 이 때, TOTAL_COUNT를 증가시킬 용도.

int TOTAL_COUNT; // 결과의 갯수

int S, Y; // S 수, Y 수


// ADJACENT와 SELECT의 DFS 활용 방법이 다르다는 것을 알아야 한다!



// DFS 지만, 시작에 CHECK = true 하도록 구현한 case
// => 전체에서, 최대 한번씩만 탐색하면 되는 완전탐색 case
// CHECK = true / CHECK = false를 토글해 줄 필요는 없는 경우지만, 시작에 하고 싶지 않으면 맨 첫 함수 호출 전에 따로 true 해주면 됨.
void ADJACENT(int x, int y) {
    
    
    int tx, ty;
    
    
    ADJACENT_CHECK[x][y] = true;
    
    if(++ADJACENT_COUNT == 7) {
        
        TOTAL_COUNT++;
            
        return;
    }
    
    
    
    for(int i = 0; i < 4; i++) {
        
        tx = x + mx[i];
        ty = y + my[i];
        
        
        if(tx < 0 || tx >= 5 || ty < 0 || ty >= 5)
            continue;
        
        if(SELECT_CHECK[tx][ty] && !ADJACENT_CHECK[tx][ty])
            ADJACENT(tx, ty);
        
    }
}


void EVALUATE(int x, int y) {
    
    S = Y = 0;
    
    
    for(int i = 0; i < 5; i++) {
        
        for(int j = 0; j < 5; j++) {
            
            if(SELECT_CHECK[i][j]) {
                
                if(MAP[i][j] == 'S')
                    S++;
                else if(MAP[i][j] == 'Y')
                    Y++;

            }
            
        }
    }
    
    if(S < 4) // 4개 이상이어야 함.
        return;
    
    // 시작 전 초기화.
    memset(ADJACENT_CHECK, 0, sizeof(ADJACENT_CHECK));
    ADJACENT_COUNT = 0;
    
    ADJACENT(x, y);
    
}


// 7 개를 뽑음. 다 뽑은 경우 유효한지 체크함.
// DFS 지만, 반복문 내부에서 CHECK = true 하고, CHECK = false 하는 토글이 필요한 case
// => 전체에서 N 개를 뽑는 모든 경우의 수가 필요한 case
void SELECT(int start, int K) {
    
    if(K == 8) { // 7개 뽑고 8번째 반복 시작이라면
        
        EVALUATE((start - 1) / 5, (start - 1) % 5); // 제일 마지막에 뽑았던 것 이용해서 평가 시작.
        
        return;
    }
    
    
    int tx, ty;
    
    for(int i = start; i <= 24; i++) {
        
        tx = i / 5;
        ty = i % 5;
        
        if(!SELECT_CHECK[tx][ty]) {
                    
            SELECT_CHECK[tx][ty] = true;
            
            SELECT(i + 1, K + 1);
            
            SELECT_CHECK[tx][ty] = false;

        }
    }
    
}


int main() {
    
    
    for(int i = 0; i < 5; i++) {
        cin >> MAP[i];
    }
    
    SELECT(0, 1);
    
    cout << TOTAL_COUNT << "\n";
    
}

 

 

젠장... 소요시간 셀 수도 없다 ㅋㅋ