백준 3967 매직 스타

문제 설명

• 매직스타는 1부터 12까지의 숫자가 헥사그램으로 채워져 있는 모양을 말한다.
  

  

• 매직 스타는 네 개의 숫자로 이루어진 한 줄을 모두 더하면 26이 된다.
• 수가 몇개 채워지지 않은 입력값이 주어질 때 매직 스타의 규칙에 맞도록 채워서 반환해라(매직스타가 여러개 나온다면 사전순으로 가장 빠른 것 하나만 출력한다.)

문제 링크

문제 접근

• 처음에는 좌표별로 하나씩 하드코딩을 진행하면서 재귀를 돌리니까 코드가 500줄이 넘게 나왔다.
• 이 방법은 에러의 가능성이 너무 많아서 각좌표별 인덱스를 잘 나누고 브루트 포스로 접근하기로 결정
• 빈 자리에는 아직 사용 안한 문자를 하나씩 넣어보고 빈 자리가 없으면 매직 스타의 조건에 맞는지 확인
• 한 줄을 채울 때 매직 스타의 조건에 맞는지 하나씩 확인하면서 재귀를 돌면 백트래킹이 된다.
• 매직 스타의 조건에 맞으면 출력 후 종료.

풀이 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool flag = false;
void    sol(vector<int> &alpha, vector<int> &input)
{
    string    last = ".........\n.........\n.........\n.........\n.........\n";

    if (flag)
        return;
    for (int i = 0; i < 12; i++)
    {
        if (input[i] == -1)
        {
            for (int j = 0; j < 12; j++)
            {
                if (alpha[j] ==  -1)
                {
                    alpha[j] = 1;
                    input[i] = j;
                    sol(alpha, input);
                    alpha[j] = -1;
                    input[i] = -1;
                }
            }
            return;
        }
    }
    for (int i = 0; i < 12; i++)
    {
        if (input[i] == -1)
            return;
    }
    last[4] = input[0] + 'A';    last[11] = input[1] + 'A';    last[13] = input[2] + 'A';
    last[15] = input[3] + 'A';    last[17] = input[4] + 'A';    last[22] = input[5] + 'A';
    last[26] = input[6] + 'A';    last[31] = input[7] + 'A';    last[33] = input[8] + 'A';
    last[35] = input[9] + 'A';    last[37] = input[10] + 'A';    last[44] = input[11] + 'A';
    if (input[7] + input[8] + input[9] + input[10] == 22 && input[0] + input[2] + input[5] + input[7] == 22 && \
    input[0] + input[3] + input[6] + input[10] == 22 && input[1] + input[5] + input[8] + input[11] == 22 && \
    input[4] + input[6] + input[9] + input[11] == 22 && input[1] + input[2] + input[3] + input[4] == 22 && \
    flag != true)
    {
        cout<<last;
        flag = true;
    }
}

int main()
{
    vector<string> temp(5);
    vector<int>    input(12);
    vector<int>    alpha(12);

    fill(alpha.begin(), alpha.end(), -1);
    for (int i = 0; i < 5; i++)
    {
        cin>>temp[i];
        for (int j = 0; j < 9; j++)
        {
            if (temp[i][j] >= 'A' && temp[i][j] <= 'L')
            {
                alpha[temp[i][j] - 'A'] = 1;
            }
        }
    }
    input[0] = temp[0][4] - 'A';input[1] = temp[1][1] - 'A';input[2] = temp[1][3] - 'A';
    input[3] = temp[1][5] - 'A';input[4] = temp[1][7] - 'A';input[5] = temp[2][2] - 'A';
    input[6] = temp[2][6] - 'A';input[7] = temp[3][1] - 'A';input[8] = temp[3][3] - 'A';
    input[9] = temp[3][5] - 'A';input[10] = temp[3][7] - 'A';input[11] = temp[4][4] - 'A';
    for (int i = 0; i < 12; i++)
    {
        if (input[i] > 12)
            input[i] = -1;
    }
    sol(alpha, input);
}

-> 문제에 경우의 수가 많고, 조건이 있으면 한 번에 조건까지 포함해서 문제를 풀려고 하지 말고 문재를 쪼개서 푸는 습관을 가지자