C - [백준 1062] 가르침 (feat. 백트래킹, 문자열)

참조 포스트

2025.01.07 - [Computer Science/자료구조 & 알고리즘] - [알고리즘] 백트래킹과 DFS: 문제 요구사항에 맞춘 설계 방법 (feat. 알고리즘 문제 유형)

[알고리즘] 백트래킹과 DFS: 문제 요구사항에 맞춘 설계 방법 (feat. 알고리즘 문제 유형)

 

2025.01.07 - [Computer Science/알고리즘 문제] - C - [백준 6603] 로또 (feat. 백트래킹)

 

 

BOJ 1062 - 가르침( https://www.acmicpc.net/problem/1062)

 

가르침(BOJ 1062) 문제는 특정 조건을 만족하는 단어들을 가르칠 수 있는 알파벳을 선택하여, 최대로 읽을 수 있는 단어의 개수를 계산하는 문제입니다.
문제의 주요 조건은 다음과 같습니다:

1. 각 단어는 반드시 "anta"로 시작하고 "tica"로 끝납니다.
2. 최소한 'a','n','t','a'  5개의 알파벳은 알아야 단어를 읽을 수 있습니다.
3. 최대 K개의 알파벳을 가르칠 수 있습니다.

목표는 K개의 알파벳을 선택하여 읽을 수 있는 단어의 최대 개수를 구하는 것입니다.

 

---

 

 Checkpoint

 

조합과 문자열의 비교를 이용하면 풀 수 있던 문제였다. 상단의 채점 결과를 보면 2번 제출했으나 시간을 보면 나중에 제출한 것이 더 빠른 것을 알 수 있다(140ms). 차이는 문제를 꼼꼼하게 분석하지 않은 것이 원인이라고 할 수 있다.

 

이미 문제에서 각 단어의 시작은 "anta" 끝은 "tica"로 된다는 것을 명시해 놓았으나, 입력 시 해당 요구사항을 만족하지 않는 단어가 들어올까봐 문자열을 입력 받은 후 , 시작은 "anta" 끝은 "tica"로 되어있는지 검증하는 불필요한시스템을 설계하여, 불필요한 반복문이 한번 더 생성될 뿐만 아니라 이를 위한 변수도 할당했다(메모리에서도 비효율적).

 

즉 처음 제출할때는 불필요한 검증 알고리즘이 추가되어 156ms가 기록되었고, 후에 제출한 것은 이 알고리즘을 제외시켜 140ms가 기록되었다.

 

이를 제외하고는, 기존의 백트래킹 알고리즘을 적절하게 활용하여 글자 조합을 생성하고 단어에 해당 글자들이 존재하는지만 확인하면 되기 때문에 이슈사항이 크게 없었다.

 

---

문제 분석

1. 필수 알파벳

단어를 읽으려면 최소한 "antic"에 포함된 5개의 알파벳은 반드시 포함되어야 합니다. 따라서, K < 5인 경우 단어를 읽을 수 없으므로 결과는 항상 0입니다.

2. 남은 알파벳 선택

• 필수 알파벳 외에 총 21개의 알파벳이 있습니다.
• K > 5인 경우, 추가적으로 선택할 수 있는 알파벳 조합을 생성해 최적의 조합을 찾습니다.

3. 효율적인 조합 생성

• DFS를 사용하여 알파벳 조합을 생성하고, 각 조합에 대해 읽을 수 있는 단어의 개수를 계산합니다.

---

구현 코드

/*
C_BOJ_1062_가르침
https://www.acmicpc.net/problem/1062

알파벳: 26개

알파벳 최소 갯수: 5개 (a, n , t, i, c)
시작 > anta
끝 > tica
*/
#include <stdio.h>
#include <string.h>

// 단어 개수 N, 글자 개수 K
int N, K;
int count = 0;
char lines[50][16];
int invalid_line[50] = {0};
int alphabet_visited[26] = {0};

void alphabet_combination(int depth, int start) {
    if (depth == K) {
        int temp_count = 0;
        for (int i = 0; i < N; i++) {
            if (!invalid_line[i]) {
                int len = strlen(lines[i]);
                int flag = 1; // 단어를 읽을 수 있다고 가정
                for (int j = 4; j < len - 4; j++) { // "anta"와 "tica" 제외
                    if (!alphabet_visited[lines[i][j] - 'a']) {
                        flag = 0; // 읽을 수 없는 글자 발견
                        break;
                    }
                }
                if (flag) {
                    temp_count++;
                }
            }
        }
        if (temp_count > count) {
            count = temp_count;
        }
        return;
    }

    for (int i = start; i < 26; i++) {
        if (!alphabet_visited[i]) {
            alphabet_visited[i] = 1;
            alphabet_combination(depth + 1, i + 1);
            alphabet_visited[i] = 0;
        }
    }
}

int main() {
    char start[5] = "anta";
    char end[5] = "tica";
    char min_alphabets[6] = "antic"; // 최소 필수 알파벳

    scanf("%d %d", &N, &K);

    // 글자 개수가 5 미만일 경우
    if (K < 5) {
        printf("0\n");
        return 0;
    }

    // 필수 알파벳 방문 처리
    for (int i = 0; i < 5; i++) {
        alphabet_visited[min_alphabets[i] - 'a'] = 1;
    }

    // 단어 입력 및 유효성 검사
    for (int i = 0; i < N; i++) {
        scanf("%s", lines[i]);
        int len_line = strlen(lines[i]);
        for (int j = 0; j < 4; j++) {
            if (lines[i][j] != start[j] || lines[i][len_line - 4 + j] != end[j]) {
                invalid_line[i] = 1;
                break;
            }
        }
    }

    // 알파벳 조합 생성
    alphabet_combination(5, 0);

    // 결과 출력
    printf("%d\n", count);
    return 0;
}

---

코드 상세 해설

1. 전역 변수 및 초기 설정

int N, K;
int count = 0;
char lines[50][16];       // 입력된 단어를 저장할 배열
int invalid_line[50] = {0}; // 유효하지 않은 단어 표시
int alphabet_visited[26] = {0}; // 선택된 알파벳 추적

• lines: 최대 50개의 단어를 저장. 각 단어의 길이는 최대 15.
• invalid_line: 시작과 끝이 "anta"와 "tica"가 아닌 단어를 표시.
• alphabet_visited: 선택된 알파벳을 추적하는 배열.

---

2. 필수 알파벳 처리

char min_alphabets[6] = "antic";

for (int i = 0; i < 5; i++) {
    alphabet_visited[min_alphabets[i] - 'a'] = 1;
}

• 단어를 읽기 위해 반드시 필요한 "antic"의 5개 알파벳을 미리 선택.

---

3. 단어 입력 및 유효성 검사 --- 불필요한 유효성 검사 부분

for (int i = 0; i < N; i++) {
    scanf("%s", lines[i]);
    int len_line = strlen(lines[i]);
    for (int j = 0; j < 4; j++) {
        if (lines[i][j] != start[j] || lines[i][len_line - 4 + j] != end[j]) {
            invalid_line[i] = 1; // 유효하지 않은 단어로 표시
            break;
        }
    }
}

• 단어 입력 시 "anta"로 시작하고 "tica"로 끝나는지 확인.
• 조건을 만족하지 않는 단어는 invalid_line[i] = 1로 표시하여 제외.

---

4. 읽을 수 있는 단어 개수 계산

for (int i = 0; i < N; i++) {
    if (!invalid_line[i]) {
        int len = strlen(lines[i]);
        int flag = 1; // 단어를 읽을 수 있다고 가정
        for (int j = 4; j < len - 4; j++) { // "anta"와 "tica" 제외
            if (!alphabet_visited[lines[i][j] - 'a']) {
                flag = 0; // 읽을 수 없는 글자 발견
                break;
            }
        }
        if (flag) {
            temp_count++;
        }
    }
}

• 각 단어에 대해:
  1. 시작과 끝의 "anta"와 "tica"를 제외한 부분을 검사.
  2. 해당 글자가 선택된 알파벳(alphabet_visited)에 포함되지 않으면 읽을 수 없다고 판단.

---

5. 백트래킹을 통한 알파벳 조합 생성

void alphabet_combination(int depth, int start) {
    if (depth == K) {
        int current_count = count_readable_words();
        if (current_count > count) {
            count = current_count;
        }
        return;
    }

    for (int i = start; i < 26; i++) {
        if (!alphabet_visited[i]) {
            alphabet_visited[i] = 1;
            alphabet_combination(depth + 1, i + 1);
            alphabet_visited[i] = 0;
        }
    }
}

• 백트래킹 방식으로 알파벳 조합 생성:
  1. depth가 K에 도달하면, 현재 선택된 알파벳으로 읽을 수 있는 단어 수를 계산.
  2. 각 알파벳을 선택하고 재귀적으로 다음 조합 생성.
  3. 조합 탐색 후 선택을 해제(alphabet_visited[i] = 0)하여 다른 조합으로 탐색.

---

6. 결과 출력

alphabet_combination(5, 0);
printf("%d\n", count);

• 필수 알파벳 "antic" 5개를 먼저 선택한 상태에서 추가 알파벳 조합 생성.
• 최대로 읽을 수 있는 단어 개수를 출력.

---

코드의 흐름 요약

1. 입력된 단어 중 "anta"로 시작하고 "tica"로 끝나는 단어를 유효한 단어로 필터링.
2. 필수 알파벳 "antic"을 선택한 상태에서 최대 K개의 알파벳 조합을 생성.
3. 각 조합에 대해 읽을 수 있는 단어 수를 계산하여 최댓값을 갱신.
4. 최종 결과를 출력.

---

 

예제 입력/출력

입력

3 6
antaxxxxxxxtica
antayyyyyytica
antazzzzzztica

출력

3

 

---

입력

4 7
antaxxxxxxxtica
antayyyyyytica
wrongwordxxxxx
antazzzzzztica

출력

3

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.