[BOJ] 1759번 암호 만들기

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

---

문제 이해

이 문제를 처음 보았을 때, 백트래킹을 이용한 조합이라고 생각했다.

 

기본적으로 암호로 만들 수 있는 경우를 다 출력하는 문제인데 조건은 다음과 같다.

암호는 최소 한 개의 모음과 최소 두 개의 자음의 조합이다.

그리고 각 암호는 증가하는 순서로 배열되어있다.

 

백트래킹에 가지치기 잘 치면 될 것 같다 생각해서 코드를 작성했다.

---

설명

바로 문제 양식대로 백트래킹을 구현해 줬다.

여기서 고민했던 부분은 최소 한 개의 모음과 최소 두 개의 자음이었다.

생각을 해보니 모음을 선택 안 하는 기준은 전체 길이에서 현재 문자열의 모음 개수를 뺀 게 2보다 작거나 같다면

즉, 자음 개수가 2보다 작으면 선택을 안 하면 되는 거였다.

그리고 자음을 선택 안 하는 기준은 전체 길이에서 현재 문자열을 뺀 값이 1이면서 모음이 하나도 없을 때 선택을 안 하면 된다.

마지막으로 불필요한 반복을 줄이기 위해서 남은 길이와 남은 문자열 개수를 비교하여 남은 길이가 현재 문자열 개수보다 작거나 같을 때만 백트래킹이 시행되게 가지치기를 총 3번 진행했다.

def is_vowel(s): # 모음인지 확인하는 함수
    return s in ["a", "e", "i", "o", "u"]

def backtracking():
    global vowels, curr_idx
    if len(result) == L:
        print("".join(result))
        return
    
    else:
        last_idx = curr_idx + 1
        for i in range(last_idx, C):
            if visited[i]: continue

            vowel_check = is_vowel(S[i])
            # 모음 선택 안하는 기준 (문자열을 완성하게 된다면 자음이 부족할 때)
            if L - vowels <= 2 and vowel_check: continue
            # 자음 선택 안하는 기준 (문자열을 완성하게 된다면 모음이 부족할 때)
            if L - len(result) == 1 and vowels == 0 and not vowel_check: continue
            # 남은 문자열이 충분한지 비교
            if L - len(result) > C - i: break

            if vowel_check: vowels += 1
            result.append(S[i])
            visited[i] = 1
            curr_idx = i

            backtracking()

            if vowel_check: vowels -= 1
            result.pop()
            visited[i] = 0
            curr_idx = last_idx

L, C = map(int, input().split())
S = sorted(input().split())

visited = [0] * C
vowels = 0
curr_idx = -1
result = []

backtracking()

---

AC!

바로 AC를 받았다! :blobaww:

남들도 비슷하게 접근한 걸 확인할 수 있었고, itertools에 combination을 사용한 간단한 코드도 볼 수 있었다. :blobfearful:

역시 파이썬은 다른 언어에 비해 지원하는 내부 기능들이 많다고 생각 들었다.