[BOJ/백준] 1759번 암호 만들기 (Python 파이썬)

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

1759번: 암호 만들기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	49550	23252	16140	44.540%

 

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력 1

4 6
a t c i s w

예제 출력 1

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

 

---

이번 문제도 제약 조건을 설정하고 이를 토대로 가지 치기를 진행하면서 탐색을 설계해 보겠습니다.

Backtracking에 아직 익숙치 않은 분들은 다음 글을 참고해 주세요.

2022.08.10 - [Algorithm/BackTracking] - [BOJ/백준] 9663번 N-Queen (Python/파이썬)

[BOJ/백준] 9663번 N-Queen (Python/파이썬)

 

제약 조건 및 검사 

문제를 살펴보면 제약 조건을 다음과 같이 정리할 수 있습니다.

1. 암호는 L개의 문자로 구성된다.
2. 암호는 서로 다른 문자로 구성된다.
3. 암호에는 최소 한 개의 모음이 포함된다.
4. 암호에는 최소 두 개의 자음이 포함된다.
5. 암호의 문자들은 오름차순이다.

이제 이를 구현해봅시다. 
조건을 잘 살펴보면, 암호가 완성된 후 검사해야 할 조건과 그렇지 않은 조건으로 나눌 수 있습니다.
1,3,4는 전자 그리고 2,5는 후자에 해당하겠네요 

조건 1, 3, 4

1번째 조건은 단순히 길이를 체크하면 되므로 따로 함수는 필요없습니다.

checkA는 위 제약 조건 중 3,4번째의 조건을 확인합니다.

def checkA(list):
    flag1, flag2, cnt = False, False, 0
    for x in list:
        # 모음
        if x in ['a', 'e', 'i', 'o', 'u']:
            flag1 = True
        # 자음
        else:
            cnt += 1
    if cnt >= 2:
        flag2 = True
    return flag1 and flag2

입력으로 주어진 list를 하나씩 탐색하면서 
(1) 모음이면 flag1을 True로
(2) 자음이면 cnt를 1 증가시킵니다.
이후 cnt가 2 이상이면 flag2를 True로 만들고,  flag1 and flag2 를 통해 최종적으로 해당 암호가 주어진 제약 조건을 만족하는지 검사합니다.

조건 2, 5

이전 포스팅에서도 자주 등장했던 중복 x and 오름차순 조합입니다.
이 경우 탐색을 진행하면서 어느 가지에 대해서 pruning을 진행해야 할 지 결정하는 기준입니다.
따라서 다음과 같이 구현합니다.

def solve(depth):
    if len(ans) == L and checkA(ans):
        print(''.join(map(str, ans)))
        return
    for i in range(depth, C):
        if visited[i] == 0:  # 중복 체크
            if len(ans) == 0:
                ans.append(pwd[i])
                visited[i] = 1
                solve(depth+1)
                ans.pop()
                visited[i] = 0
            else:
                if ans[-1] < pwd[i]:  # 오름차순
                    ans.append(pwd[i])
                    visited[i] = 1
                    solve(depth+1)
                    ans.pop()
                    visited[i] = 0

이전 BackTracking 포스팅들에서도 항상 등장했던 패턴입니다,, 기본적인 N과 M 문제를 정복하셨다면 쉽게 구현하실 수 있습니다.

2022.08.10 - [Algorithm/BackTracking] - [BOJ/백준] N과 M (1~8) (Python 파이썬) [15649, 15650, 15651, 15652, 15654, 15655, 15656, 15657]

[BOJ/백준] N과 M (1~8) (Python 파이썬) [15649, 15650, 15651, 15652, 15654, 15655, 15656, 15657]

 

최종 code

따라서 최종적인 코드는 다음과 같습니다.

from sys import stdin
input = stdin.readline
L, C = map(int, input().split())
pwd = sorted(list(input().split()))
visited = [0]*C
ans = []

# (1) L글자 (2) 최소 1개의 모음 (3) 최소 2개의 자음


def solve(depth):
    if len(ans) == L and checkA(ans):
        print(''.join(map(str, ans)))
        return
    for i in range(depth, C):
        if visited[i] == 0:  # 중복 체크
            if len(ans) == 0:
                ans.append(pwd[i])
                visited[i] = 1
                solve(depth+1)
                ans.pop()
                visited[i] = 0
            else:
                if ans[-1] < pwd[i]:  # 오름차순
                    ans.append(pwd[i])
                    visited[i] = 1
                    solve(depth+1)
                    ans.pop()
                    visited[i] = 0


def checkA(list):
    flag1, flag2, cnt = False, False, 0
    for x in list:
        # 모음
        if x in ['a', 'e', 'i', 'o', 'u']:
            flag1 = True
        # 자음
        else:
            cnt += 1
    if cnt >= 2:
        flag2 = True
    return flag1 and flag2


solve(0)