[BaekJoon/백준] 2784번 가로 세로 퍼즐

 

이 문제를 한시간이나 걸렸다면 믿으시겠습니까.

 

저처럼 문제를 잘못 이해하고 있는 사람이 없기를 바랍니다.

 

 

 

1. 입력으로 6개의 단어가 주어집니다.
2. 3 x 3 가로 세로 퍼즐을 만들건데, 세로로 3단어 가로로 3단어  총 6단어가 나올 수 있습니다.
3. 6개의 단어 중 순열을 이용해 3개의 단어를 뽑아 가로로 한 줄씩 배치하여 3x3 퍼즐을 만듭니다.
4. 가로세로 퍼즐에서의 총 6개의 단어가 각각 입력으로 주어진 6개의 단어와 동일하게 나타나는지 확인합니다.

 

입력으로 CAA가 두 번 나타났다면, 가로세로 퍼즐에서도 두 번 나타나야 합니다.

 

 

따라서, 먼저 입력을 6개 받자마자 오름차순으로 정렬시킵니다.

그리고, 입력에서 단어 3개씩 뽑아서 가로 세로 퍼즐을 잘 구성합니다.

 

가로 세로 퍼즐에서 도출될 수 있는 단어들을 나열한 뒤 오름차순으로 정렬시킵니다.

 

입력으로 받은 것을 정렬한 것과 일치하는지 확인합니다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>


using namespace std;

vector<string> PUZZLE; // 3 x 3

vector<string> INP;

bool VISIT[6]; // 순열이므로 방문체크 필요

void EVALUATE() {
    
    vector<string> MAKER;
    bool CHECK[6]; // 입력으로 주어진 문자가 각각 갯수에 맞게 가로세로 퍼즐에 나와야 한다.
    memset(CHECK, 0, sizeof(CHECK));
    
    // 가로로 만들어지는 것 추가
    for(int i = 0; i < 3; i++) {
        MAKER.push_back(PUZZLE[i]);
    }
    
    string t;
    for(int i = 0; i < 3; i++) {
        
        t = "";

        for(int j = 0; j < 3; j++)
            t += PUZZLE[j][i];

        MAKER.push_back(t);
    }
    
    
    // MAKER에는, PUZZLE에서 가로~세로로 만들 수 있는 모든 경우 6가지가 들어있음.
    
    bool flag = true;
    
    sort(MAKER.begin(), MAKER.end());
    
    for(int i = 0; i < 6; i++) {
        if(MAKER[i] != INP[i])
            flag = false;
    }
    
    
    if(flag) {
        for(int i = 0; i < 3; i++) {
            cout << PUZZLE[i] << "\n";
        }
                
        exit(0); // 찾았다면 바로 종료.
    }
}

// 조합이 아니라 순열이므로 순서에 의미가 있고, 무조건 앞에서부터 다시 체크하므로 VISIT 필요
void dfs() {
    
    
    if(PUZZLE.size() >= 3 ) {
        
        EVALUATE();
        
        return;
    }
    
    
    for(int i = 0; i < 6; i++) {
        
        if(!VISIT[i]) {
            
            PUZZLE.push_back(INP[i]);
            VISIT[i] = true;
            
            dfs();
            
            PUZZLE.pop_back();
            VISIT[i] = false;
        }
        
    }
    
}


int main() {
    
    string tmp;
    
    for(int i = 0; i < 6; i++) {
        
        cin >> tmp;
        
        INP.push_back(tmp);
        
    }
    
    sort(INP.begin(), INP.end());
    
    dfs();
    
    cout << "0\n"; // 찾지 못하면 여기까지 올 것임.
    
}

 

 

 

소요 시간 : 1시간