[문제풀이] 3967번: 매직 스타

[문제풀이]

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

문제유형

DFS, 아이디어

*인덱스를 생각하고 만드는 게 중요했던 문제.

Solution

#include <stdio.h>
 
 
#define TRUE 1
#define FALSE 0
#define INF 0x7fffffff
char a[5][9];       //출력할 맵
char *p[13];        //각 노드를 가리키는 포인터의 배열 (1부터 저장)
 
int line_cnt[7];
int line_sum[7];
int line_idx[13][2] = { { 0,0 },{ 2,3 },{ 1,4 },{ 3,4 },{ 2,4 },{ 4,5 },\
                      { 1,3 },{ 2,5 },{ 3,6 },{ 1,6 },{ 5,6 },{ 2,6 },{ 1,5 } };
 
int pos_init[13];
int alphabet_init[13];      //처음에 알파벳을 입력받은 노드는 1 체크
int pos_check[13];
int alphabet_check[13];
 
int solved;
 
void inputData()
{
    register int i, j;
    int pos = 1;
    //알파벳 input값은 일단 계산하기 편하게 숫자로 입력받음
    for (i = 0; i < 5; i++)
    {
        for (j = 0; j < 9; j++)
        {
            char ch = 0;
            scanf(" %c", &ch);
            if (ch == 'x')
            {
                a[i][j] = (char)0x0;
                p[pos] = &a[i][j];
                pos++;
            }
            else if (ch == '.') a[i][j] = ch;
            else
            {
                a[i][j] = ch - 'A' + (char)0x1;
                p[pos] = &a[i][j];
 
                //check배열
                pos_init[pos] = 1;
                alphabet_init[a[i][j]] = 1;
                pos_check[pos] = 1;
                alphabet_check[a[i][j]] = 1;
 
                //sum배열
                line_sum[line_idx[pos][0]] += a[i][j];
                line_sum[line_idx[pos][1]] += a[i][j];
                line_cnt[line_idx[pos][0]]++;
                line_cnt[line_idx[pos][1]]++;
 
                pos++;
            }
        }
    }
}
 
void print()
{
    register int i, j;
    int n = 0;
    //숫자를 알파벳으로 전환해서 출력
    for (i = 0; i < 5; i++)
    {
        for (j = 0; j < 9; j++)
        {
            char ch = a[i][j];
            if (ch == '.') printf("%c", ch);
            else printf("%c", ch + 'A' - (char)0x1);
        }
        printf("\n");
    }
}
 
int checkSol() {
    register int i;
    for (i = 1; i <= 6; i++) {
        if (line_sum[i] != 26) return FALSE;
        if (line_cnt[i] != 4) return FALSE;
    }
    return TRUE;
}
 
int DFS(int pos)
{
    //종료조건
    if (solved) return 1;
    if (pos > 12)
    {
        if (checkSol()) {
            print();
            solved = 1;
        }
        return 1;
    }
 
    //초기값은 스킵
    if (pos_init[pos]) DFS(pos + 1);
 
    //alphabet 탐색
    for (register int i = 1; i <= 12; i++)
    {
        if (alphabet_check[i] || pos_check[pos] || alphabet_init[i] || pos_init[pos]) continue;
        if (line_sum[line_idx[pos][0]] + i > 26) continue;
        if (line_sum[line_idx[pos][1]] + i > 26) continue;
        if (line_cnt[line_idx[pos][0]] + 1 > 4) continue;
        if (line_cnt[line_idx[pos][1]] + 1 > 4) continue;
 
        //check배열
        *(p[pos]) = i;
        pos_check[pos] = 1;
        alphabet_check[i] = 1;
 
        //line sum, line_cnt
        line_sum[line_idx[pos][0]] += i;
        line_sum[line_idx[pos][1]] += i;
        line_cnt[line_idx[pos][0]]++;
        line_cnt[line_idx[pos][1]]++;
 
        DFS(pos + 1);
 
        line_cnt[line_idx[pos][0]]--;
        line_cnt[line_idx[pos][1]]--;
        line_sum[line_idx[pos][0]] -= i;
        line_sum[line_idx[pos][1]] -= i;
 
        alphabet_check[i] = 0;
        pos_check[pos] = 0;
        *(p[pos]) = 0;
    }
    return 1;
}
 
int main()
{
    inputData();
    DFS(1);
 
    return 0;
}