[BOJ-1759] 암호 만들기

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

1759번: 암호 만들기

---

[백트래킹에 대한 주저리]

백트래킹을 공부하는데 아주 좋은 문제이다.

나는 재귀호출을 이용한 백트래킹을 했다.

이부분이 제일 약해서 집중적으로 공부할 예정이다 ㅠㅠ

 

백트래킹이 약한만큼, 다른사람들의 코드를 보면서 배워나갈 것이다!

화이팅 하자 ㅎㅎ!

---

 

[풀이]

L : 조교가 만들려고 한 암호 길이

words : 암호를 만드는데 사용한 알파벳 소문자들

C : words 리스트의 길이 (알파벳 개수)

 

1. words를 오름차순으로 정렬 시킨다.

2. 암호의 시작점을 먼저 선정한다.

문제의 예시를 활용해서 설명하자면, words=[ 'a', 'c', 'i', 's', 't', 'w'] 이고, L=4 이라 할때

'a'가 시작점인 경우는 'c', 'i', 's', 't', 'w' 를 이용하여 길이가 4인 암호를 만들 수 있다.

'c'가 시작점인 경우는 'i', 's', 't', 'w'를 이용하여 길이가 4인 암호를 만들 수 있다.

'i'가 시작점인 경우는 's', 't', 'w'를 이용하여 길이가 4인 암호 'istw' 를 만들 수 있다.

여기서 눈치를챘는가?

그렇다 암호의 시작점은 0부터 C-L 까지만 가능하다.

 

3. 암호의 길이가 L일때, 암호를 프린트 할 수 있는 조건을 만든다.

암호의 조건은 자음개수>=2, 모음개수>=1 이다.

 

이 조건을 바로 확인시켜 출력하기 위해서

암호를 만들기 시작할 때, 시작알파벳(words[i])이 자음인지 모음인지를 확인하고

자음개수와 모음개수를 카운트하는 식으로 했다.

backtracking( 시작 인덱스= i , 초기암호=words[i] , 모음개수, 자음개수 ) (단, i=0,1,2, ..., C-L )

 

그렇게 backtracking함수(재귀함수)에서, 다음 알파벳 문자가 자음인지 모음인지 확인하고

현재암호에 다음 알파벳 문자를 추가했다.

 

현재암호의 인덱스가 i라면, 다음 알파벳 문자 인덱스를 j (j=i+1, ..., C-1) 라 하면

backtracking( 다음 인덱스=j , 이전암호+words[j], 모음개수, 자음개수)

 

이 과정을 그림으로 나타내봤다.

백트래킹을 연상시키는데 좋을 것이다.

DFS와 Backtracking의 차이점은 가지치기인데

이 가지치기는 모든 경우를 탐색하는게 아니라, 조건에 맞는것만 재귀호출하여 탐색한다.

---

[코드]

# -*- coding: utf-8 -*-
# backtracking 훈련: 암호만들기
import sys
input= sys.stdin.readline

L,C=0,0
words=None
vowels={'a','e','i','o','u'} #모음 집합
consonant=set(chr(n) for n in range(97,97+26) if chr(n) not in vowels )#자음

# idx: 알파벳(words)의 인덱스
# password: 만들수 있는 암호
# vow: 모음개수
# cons: 자음개수
def backtracking(idx , pw, vow, cons ):
    global L,C, words, visited
    #만일 pw길이가 L이라면
    if len(pw)==L:
        #최소 1개 이상의 모음을 갖는가?/ 최소 2개 이상의 자음을 갖는가?
        if (vow>=1) and (cons>=2):
            print(pw)
        
    #pw의 길이가 L보다 작다면
    elif len(pw)<L:
        for i in range(idx+1, C):
            if words[i] in vowels: #다음알파벳이 모음이라면
                backtracking(i, pw+words[i], vow+1,cons)
            else:#다음 알파벳이 자음이라면
                backtracking(i, pw+words[i], vow, cons+1)

def main():
    global L,C, words, visited
    
    #L: 암호길이/ C: words의 길이. (3<=L<=C<=15)
    L,C=map(int, input().split())
    words=sorted([*(input().split())]) #오름차순으로 정렬.

    #가능한 암호의 시작점: 0,1, .., C-L
    for i in range(C-L+1):
        if words[i] in vowels: #시작 알파벳이 모음이라면-> 모음개수 1
            backtracking(i, words[i],1,0)
        else: #시작 알파벳이 자음이라면-> 자음 개수 1
            backtracking(i, words[i],0,1)
        

if __name__=='__main__':
    main()