[어려워요알고리즘] BOF 1759 : 암호 만들기

Info

• 백준 1759번 암호 만들기
• Gold 5 solved.ac
• 완전 탐색, 백트래킹

Write UP

처음으로 백트래킹 문제를 해설 안 보고!! 풀었습니다. 뿌듯하네요ㅎㅎ..

우선 테스트 케이스가 상당히 적습니다.
최대 input이 15이고 알파벳도 26자밖에 없으니 완전 탐색을 돌려도 되겠어요.

또 알파벳끼리의 중복이 없고 오름차순이란 조건까지 줬습니다.

이렇게 되면 단순히 입력받은 문자들을 정렬하고 dfs를 통해 방문한 지점이면 표시, L만큼 방문할 때까지 돌리다가 cnt = L이 되는 순간 출력하면 돼요.

그 후 방문한 곳을 백트래킹을 이용해 0으로 초기화, 다시 cnt = L까지 재귀를 실행하면 됩니다.

조금 시간이 걸렸던 부분은, main에서 dfs 함수에 인자를 줄 때 0, 0을 넘겼어요.
이러면 for문 안에서 nx = 1부터 돌기 때문에 첫 번째 visited가 백트래킹이 안 되더라구요.

인자를 -1, -1로 바꿔서 해결했습니다.

#include <iostream>
#include <cstdio>
using namespace std;

int L, C;
char arr[16];
int visited[16] = { 0 };

void dfs(int start, int cnt) {
    int aeiouCnt = 0;
    int notAeiouCnt = 0;
    
    if (cnt == L - 1) {
        for (int i = 0; i < C; i++) {
            if (visited[i] == 1) {
                if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u') aeiouCnt++;
                else notAeiouCnt++;
            }
        }
        
        if (aeiouCnt >= 1 && notAeiouCnt >= 2) {
            for (int i = 0; i < C; i++) {
                if (visited[i] == 1) printf("%c", arr[i]);
            }
            printf("\n");
        }
        return ;
    }
    
    for (int i = start; i < C; i++) {
        int nx = i + 1; // nx = 0부터 시작
        visited[nx] = 1;
        if (nx < C && cnt < L) {
            dfs(nx, cnt + 1);
        }
        visited[nx] = 0; // 백트래킹
    }
}

int main() {
    scanf("%d %d", &L, &C);
    for (int i = 0; i < C; i++) {
        getchar();
        scanf("%c", &arr[i]);
    }

    // 오름차순 정렬
    for (int i = 0; i < C - 1; i++) {
        for (int j = i + 1; j < C; j++) {
            if (arr[i] > arr[j]) {
                char tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    
    dfs(-1, -1);
    
    return 0;
}