[백준] 1062번 가르침 (= teaching) - 재우스 프로그래밍 (C 언어)

문제 링크 : www.acmicpc.net/problem/1062

#include <stdio.h>
#include <stdbool.h>
#include <string.h>    //strlen

#define DEBUG 0
#define MAX_WORD_COUNT 50
#define MAX_INPUT_WORD_SIZE 15
#define MAX_LETTER_COUNT 26

int N, K, result;
int arrSelectLetterIdx;
char arrWord[MAX_WORD_COUNT][MAX_INPUT_WORD_SIZE + 1];
    //초기에 입력 받은 단어를 arrWord[0]부터 arrWord[N-1]까지 차례대로 저장할 배열
    //단어는 15글자보다 작거나 같으므로 arrWord[i]의 size는 최대 16까지 필요함.
char arrLetter[MAX_WORD_COUNT][MAX_INPUT_WORD_SIZE - 8 + 1];
    //arrWord 배열에서 a, n, t, i, c를 제외하고 중복된 문자 없이 저장한다.
    //애초에 입력받은 문자가 15자인데 앞뒤 네글자는 무조건 제거되므로 최대 7글자만 필요함.
char arrAllLetter[MAX_LETTER_COUNT + 1];
    //arrLetter에 저장된 모든 문자를 중복되지 않게 저장
    //알파벳 소문자의 개수는 총 26개이므로 최대 26글자의 공간이 필요함
bool visited[MAX_LETTER_COUNT + 1];
    //가르칠 알파벳 문자를 조합할 때 이미 가르칠 예정인 문자는 중복해서 넣지 않도록 가르칠 문자에 이미 포함되어있는지 여부를 결정해주는 배열
    //입력 받은 알파벳 소문자의 최대 개수는 총 26개이므로 최대 26글자의 공간이 필요함
char arrSelectLetter[MAX_LETTER_COUNT - 5 + 1 + 1];    //탐색할 문자들의 조합을 저장하는 배열
    //가르칠 알파벳을 저장해 놓은 배열(a, n, t, i, c는 제외)
    //입력 받은 알파벳의 소문자의 최대 개수는 총 26개이므로 최대 21개의 공간이 필요함
    //꽉 차도 하나를 추가했다가 빼주는 명령이 있어서 하나 추가

void bruteForce(int);
    //arrAllLetter에 저장된 모든 문자들을 K - 5개만큼 조합해주는 함수
void countReadWord(void);
    //bruteForce() 함수에서 조합한 문자로 생성할 수 있는 단어의 개수를 계산해서 최댓값을 갱신해주는 함수

void selectLetter(void);
    //arrWord에서 a, n, t, i, c를 제외한 글자를 arrLetter에 중복되지 않도록 순서대로 저장
bool checkLetter(char *word, char letter);
    //인자로 받은 word 안에 문자 letter가 포함되는지 여부를 반환해주는 함수
void countNecessary(void);    
    //K == 5일 때 a, n, t, i, c로만 이루어진 단어를 계산해주는 함수
void initVisited(void);        //visited 배열을 초기화해주는 함수
void initArrSelectLetter(void);        //arrSelectLetter 배열을 초기화해주는 함수

int main(void)
{
    scanf("%d", &N);
    scanf("%d", &K);

    for (int i = 0; i < N; i++) {
        scanf("%s", arrWord[i]);
    }

    //배울 수 있는 문자가 5개 미만이면 단 한개의 단어도 읽을 수 없다.
    if (K < 5) {
        printf("0\n");
        return 0;
    }
    //배울 수 있는 문자가 5개라면 정확히 a, n, t, i, c를 배워야 한다.
    else if (K == 5) {
        countNecessary();
    }
    //배울 수 있는 문자가 26개라면 모든 알파벳을 아는 것이므로 모든 단어를 읽을 수 있다.
    else if (K == 26) {
        result = N;
    }
    //배울 수 있는 문자가 5개보다 많고 26개보다 적을 때
    else {
        initArrSelectLetter();
        selectLetter();

        initVisited();
        //입력 받은 모든 단어가 a, n, t, i, c로만 이루어져 있을 때
        if (arrAllLetter[0] == '\0') {
            result = N;
        }

        //필요한 문자를 차례대로 brute force 알고리즘 방식으로 탐색한다.
        for (int i = 0; i < (int)strlen(arrAllLetter); i++) {
            bruteForce(i);
            arrSelectLetter[--arrSelectLetterIdx] = '\0';
        }
    }

    printf("%d\n", result);

    return 0;
}

void bruteForce(int index)
{
    //탐색할 문자 조합이 이미 꽉 차서 더 이상 추가할 수 없을 때
    if (arrSelectLetterIdx == K - 5) {
        //반환한 반복문에서 문자를 하나 빼줘야 하므로 하나 강제로 추가한다.
        arrSelectLetter[arrSelectLetterIdx++] = arrAllLetter[index];
        return;
    }

    //탐색할 문자 조합을 추가하는데 아직 추가 안한 문자일 때 if문 실행
    if (!visited[index]) {
        arrSelectLetter[arrSelectLetterIdx++] = arrAllLetter[index];    //탐색할 문자 추가
        //추가했더니 문자 조합이 꽉차거나 || 넣을 수 있는 모든 문자를 이미 다 넣었을 때(추가로 넣을 것이 없으므로)
        if (arrSelectLetterIdx == K - 5 || (int)strlen(arrAllLetter) == arrSelectLetterIdx) {
            countReadWord();    //만들 수 있는 단어 개수 계산 및 결과 갱신
        }

        visited[index] = true;    //문자 추가했음 체크한다.

        //배열의 순서대로 조합을 생각하고 있으므로 현재 입력받은 문자 이전 위치에 있는 문자들과의 조합은 이미 생각을 했으므로 index + 1부터 시작한다.
        for (int i = index + 1; i < (int)strlen(arrAllLetter); i++) {
            bruteForce(i);    //조합에 i추가할지 함수 대입
            arrSelectLetter[--arrSelectLetterIdx] = '\0';    //최종적으로 backtracking을 위해서 마지막에 추가한 문자를 제거하면서 돌아간다.
        }
        visited[index] = false;    //문자 추가를 해제했음을 체크한다.
    }
    return;
}

void countReadWord(void)
{
    int count = 0;

    for (int i = 0; i < N; i++) {
        //arrLetter에 필요한 문자 개수가 K - 5보다 크면 어차피 못만드는 단어이다.
        if ((int)strlen(arrLetter[i]) <= K - 5) {

            int j;
            //조합한 문자에 포함되어 있는지 검사
            for (j = 0; j < (int)strlen(arrLetter[i]); j++) {
                if (!checkLetter(arrSelectLetter, arrLetter[i][j])) {
                    break;
                }
            }
            //모든 문자가 selctLetter에 들어있으므로 만들 수 있는 단어이다.
            if (j == (int)strlen(arrLetter[i])) {
                count++;
            }
        }
    }

    //이번에 만들 수 있는 단어의 개수가 이전의 최대 갯수보다 많으면 갱신
    if (result < count) {
        result = count;
    }

    return;
}

void selectLetter(void)
{
    //N개의 단어에 필수 글자를 제외한 글자 저장
    for (int i = 0; i < N; i++) {
        //앞 뒤 필수 글자 각각 4글자는 제외
        for (int j = 4; j < (int)strlen(arrWord[i]) - 4; j++) {
            //필수로 필요한 문자 a, n, t, i, c가 아니라면
            if (arrWord[i][j] != 'a' && arrWord[i][j] != 'n' && arrWord[i][j] != 't' && arrWord[i][j] != 'i' && arrWord[i][j] != 'c') {
                //arrLetter에 이미 저장한 글자가 아닌지 검색
                if (!checkLetter(arrLetter[i], arrWord[i][j])) {
                    //저장한 글자가 아니면 arrLetter[i]에 저장
                    arrLetter[i][(int)strlen(arrLetter[i])] = arrWord[i][j];
                }
                //arrAllLetter에 이미 저장한 글자가 아닌지 검색
                if (!checkLetter(arrAllLetter, arrWord[i][j])) {
                    //저장한 글자가 아니면 arrAllLetter에 저장
                    arrAllLetter[(int)strlen(arrAllLetter)] = arrWord[i][j];
                }
            }
        }
    }
    return;
}

bool checkLetter(char *word, char letter)
{
    for (int i = 0; i < (int)strlen(word); i++) {
        if (word[i] == letter) {
            return true;
        }
    }
    return false;
}

void countNecessary(void)
{
    selectLetter();

    for (int i = 0; i < N; i++) {
        if (arrLetter[i][0] == '\0') {
            result++;
        }
    }
    return;
}

void initArrSelectLetter(void)
{
    for (int i = 0; i < MAX_LETTER_COUNT - 3; i++) {
        arrSelectLetter[i] = '\0';
    }
    return;
}
void initVisited(void)
{
    for (int i = 0; i < MAX_LETTER_COUNT + 1; i++) {
        visited[i] = false;
    }
    return;
}