[백준] 백준 python 1759번 문제 및 소스코드

1. 문제 링크

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

2. 문제 

3. 소스코드 및 해설

- 백트래킹 알고리즘 사용
- 암호의 길이는 주어진 값 L이어야 한다.
- 암호는 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어야 한다.

#전체 코드
vowel = ['a', 'e', 'i', 'o', 'u']

L, C = map(int, input().split())
words = input().split()

words.sort()

def check(arr):
    v_count, c_count = 0, 0
    
    for i in arr:
        if i in vowel:
            v_count += 1
        else:
            c_count += 1
            
    if v_count >= 1 and c_count >= 2:
        return True
    else:
        return False
    
def backtracking(arr):
    
    if len(arr) == L:
        if check(arr):
            print("".join(arr))
            return
        
    for i in range(len(arr), C):
        if arr[-1] < words[i]:
            arr.append(words[i])
            backtracking(arr)
            arr.pop()
            
for i in range(C - L + 1):
    a = [words[i]]
    backtracking(a)

 

1) 기본 세팅

vowel = ['a', 'e', 'i', 'o', 'u']

-모음 목록 정의. 암호에 최소 한 개 이상의 모음이 있어야 하므로, 모음을 식별하기 위해 사용된다.

L, C = map(int, input().split())
words = input().split()
words.sort()

L : 암호의 길이
C : 주어진 문자들의 총 개수
words: 암호를 만들 수 있는 문자들의 리스트
- 문자들을 사전 순으로 정렬하여, 이후에 사전순으로 암호를 생성할 수 있도록 한다.

2) 모음과 자음의 개수 체크 함수 check(arr) 사용

def check(arr):
    v_count, c_count = 0, 0
    
    for i in arr:
        if i in vowel:
            v_count += 1
        else:
            c_count += 1
            
    if v_count >= 1 and c_count >= 2:
        return True
    else:
        return False

-check(arr) 함수: 선택된 문자 배열 arr에서 모음의 개수(v_count)와 자음의 개수(c_count)를 세고, 모음이 1개 이상이고 자음이 2개 이상인 경우 True를 반환하여 암호 조건을 만족하는지 확인한다.

3) 백트래킹 함수 사용 (backtracking(arr))

def backtracking(arr):
    
    if len(arr) == L:
        if check(arr):
            print("".join(arr))
            return

- 백트래킹을 통해 암호를 구성
- arr는 현재 선택된 문자들의 배열
- 만약 arr의 길이가 암호 길이인 L과 같아졌을 때, check(arr) 함수를 호출하여 조건을 만족하는지 확인한다. 조건을 만족하면 그 배열을 출력한다.  

for i in range(len(arr), C):
    if arr[-1] < words[i]:
        arr.append(words[i])
        backtracking(arr)
        arr.pop()

- for 루프는 백트래킹을 수행하며, 배열의 마지막 문자보다 사전 순으로 큰 문자를 추가하면서 새로운 배열을 생성한다.
- 문자를 배열에 추가하고, 재귀적으로 다시 백트래킹을 호출한다.
- 재귀 호출이 끝나면 마지막 문자를 제거(pop())하여 다시 탐색을 계속한다.

4) 초기 백트래킹 호출

for i in range(C - L + 1):
    a = [words[i]]
    backtracking(a)

- 백트래킹의 시작점으로, words 리스트에서 문자를 하나씩 선택하여 backtracking 함수로 넘긴다. words[i]는 첫 번째 선택된 문자로 시작하며, 이후 나머지 문자들이 차례로 추가된다.