[ 백준 ] 3967번 - 매직 스타 (C++)

 

https://www.acmicpc.net/problem/3967

3967번: 매직 스타

 

 

[ 문제풀이 ]

 

1. 매직 스타를 입력받고, 채워지지 않은 위치를 pos에 저장합니다.

 

2. 재귀함수를 이용하여 각 자리에 알파벳을 채워주고, 각 줄의 합이 282보다 크다면 return해줍니다.

 

3. 모든 자리가 다 찬다면 그대로 출력해줍니다.

 

[ 소스코드 ]

#include<iostream>
#include<string>
#include<vector>
 
using namespace std;
 
string str[5];
char arr[12];
int visited[12];
vector<int> pos;
bool flag = false;
 
void dfs(int level)
{
    if (flag) return;
    if (arr[1] + arr[2] + arr[3] + arr[4] > 282) return;
    if (arr[0] + arr[2] + arr[5] + arr[7] > 282) return;
    if (arr[0] + arr[3] + arr[6] + arr[10] > 282) return;
    if (arr[7] + arr[8] + arr[9] + arr[10] > 282) return;
    if (arr[1] + arr[5] + arr[8] + arr[11] > 282) return;
    if (arr[4] + arr[6] + arr[9] + arr[11] > 282) return;
 
    if (level == pos.size()) {
        int cnt = 0;
        flag = true;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                if (str[i][j] != '.') {
                    cout << arr[cnt++];
                }
                else {
                    cout << str[i][j];
                }
            }
            cout << '\n';
        }
        return;
    }
 
    for (int i = 0; i < 12; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            arr[pos[level]] = i + 'A';
            dfs(level + 1);
            visited[i] = 0;
            arr[pos[level]] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 0; i < 5; i++) {
        cin >> str[i];
    }
 
    int cnt = 0;
 
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 9; j++) {
            if (str[i][j] != '.') {
                if (str[i][j] == 'x') {
                    pos.push_back(cnt++);
                }
                else {
                    visited[str[i][j] - 'A'] = 1;
                    arr[cnt++] = str[i][j];
                }
            }
        }
    }
 
    dfs(0);
}