[Python 파이썬]백준 1759번 - 암호 만들기

2023년 6월 5일

문제 링크 : 1759번 - 암호 만들기

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 조합론
• 백트래킹

---

문제 접근

그저 간단한 브루트포스 문제인 줄 알았다. 무식하게 접근했다가 코드가 점점 꼬이고 더러워지길래 다 지우고 백트래킹 기법을 활용해 보았다.

일단 문제 자체는 간단하다. 암호의 길이가 주어지고, 암호를 조합할 수 있는 알파벳의 개수와 알파벳들이 주어진다. 그리고 암호는 다음과 같은 2가지 조건을 가진다.

• 사전 순이다. abc는 가능성이 있지만, bac, cba는 그렇지 않다.,
• 최소 1개의 모음(a, e, i, o, u)과 최소 2개의 자음으로 이루어져 있어야 한다.

예를 들어 a, t, c, i, s, w 6개의 문자를 가지고 조합할 수 있는 길이가 4인 암호 조합 중, 위의 '조건'을 충족하는 암호가 존재한다면 해당 암호는 '가능성 있는 암호' 이다.

acis는 조건을 충족하는 '가능성 있는 암호' 이기에 출력해야 하며, cstw는 모음이 하나도 없기에 조건을 충족하지 못한 '가능성 있는 암호'가 아니기에 출력하지 않아야 한다.

일단 사전순으로 출력해야 하니, 입력받은 암호를 오름차순으로 정렬하고, 모든 가능한 조합을 구성해보며 각 구성된 암호 조합이 '조건'을 충족하면 print,  아니면 print 하지 않고 pass하면 되는 것이다.

나는 암호가 될 수 있는 '모든 가능한 조합' 생성 과정에서 '백트래킹' 기법을 사용할 것이다.

---

순서도

1. 입력받은 알파벳을 사전순으로 정렬한다.(오름차순)

2. 백트래킹을 이용해 모든 경우의 수를 판단한다.(최악의 경우 15 combination 7 == 6435)

3. 조합해 본 암호 후보가 자음 최소 2개 이상, 모음 최소 1개 이상의 조건을 충족하는지 확인.

4. 조건에 충족한다면 해당 암호조합 print

 

---

입력 예제

4 6
a t c i s w

입력받은 문자를 오름차순으로 정렬하면 [a, c, i, s, t, w] 순으로 재정렬 될 것이다.

이제 acis, acit, aciw, ... , istw 까지 모든 조합을 만들어보며, '조건'에 충족하는 '가능성 있는 암호'인지 체크 후, '가능성 있는 암호'라면 해당 암호를 print하면 된다.

사전 순으로 정렬이 되어 있기에, 각 암호가 '사전 순'으로 정렬되어있는지 체크하는 '첫 번째 조건'은 고려할 필요가 없다. 우린 '두 번째 조건'만 고려해보면 된다.

특정 암호 조합을 생성하면, 해당 암호의 자음과 모음 개수를 따로 체크한다. 자음이 2개 이상이면서, 모음이 1개 이상임이 확인되면 출력한다.

 

출력 예제

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

---

주의할 점

• 백트래킹 기법이 잘 떠오르지 않아 다음 블로그 포스팅 글을 참고했다. https://veggie-garden.tistory.com/24

[Python] 백트래킹 (+ DFS와 차이)

• 백트래킹 기법이 어렵다면 백트래킹에 대해 어느정도 공부한 후 문제를 시도하는 것을 추천한다. (당연하지만 백트래킹 기법을 사용하지 않는다면 상관 없다.)

---

전체 코드

# 1759

'''
함수명 : check
매개변수 : result -> 조건을 충족하는지 체크할 암호 조합
역할 : result가 조건을 충족하면 True, 충족하지 않으면 False return
'''

def check(result):
    co_cnt, vo_cnt = 0, 0 # 자음,모음 개수 체크
    for i in range(L):
        # 모음인가?
        if result[i] in ["a","e","i","o","u"]:
            vo_cnt += 1
        # 자음인가?
        else:
            co_cnt += 1
    # 조건(모음이 최소 1개, 자음이 최소 2개)을 충족하지 않는가?
    if co_cnt < 2 or vo_cnt < 1:
        return False
    else:
        # 조건을 충족하는가?
        return True

'''
함수명 : solution
매개변수 : append_idx -> result에 추가할 arr 요소의 인덱스 번호
역할 : 백트래킹을 이용하여 모든 경우의 수를 체크한다.
'''
def solution(append_idx):
    global arr
    global L,C
    global result
    
    if len(result) == L:
        if check(result) == True:
            for idx in range(L):
                print(result[idx], end="")
            print()
        return  

    # arr의 append_idx 요소부터 result에 하나씩 append.
    # 모든 암호 조합을 따져보려고 함.
    for idx in range(append_idx, C):
        result.append(arr[idx]) 
        solution(idx + 1) # idx + 1 번째 요소를 append하기 위해 매개변수 idx + 1로 재귀 수행
        result.pop() # 다른 경우의 수도 따져보기 위해, 가장 마지막에 추가한 요소 pop


if __name__ == "__main__":
    L,C = map(int,input().split())
    arr = sorted(list(map(str,input().split())))
    result = []
    solution(0)

 

---

풀이 후기

지금까지는 백트래킹 문제에 접근하기 위해 DFS를 활용하였는데, DFS를 쓰지 않고 접근하는 방법이 떠오르지 않아, 다른 블로그 글을 열심히 보며 공부하고 풀었다. 세상엔 모르는게 너무 많다!