[Algorythm] 백트래킹

시송 2025. 6. 23. 13:51

완전탐색의 효율성을 개선한 알고리즘으로, 가능성이 없는 곳을 제외하고 가능성 있는 곳만 탐색하는 알고리즘. 해가 될 가능성을 배제하기 때문에 완전탐색보다 효율적이다.

백트래킹 알고리즘의 핵심은 해가 될 가능성을 판단하는 것이다. 과정은 다음과 같다.

유효한 해의 집합 정의
정의한 집합을 그래프로 표현
유망함수(해가 될 가능성) 정의
백트래킹 알고리즘으로 해를 찾기

1. 1759번 암호 만들기

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

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

# 4 6
# a t c i s w

# 0
from itertools import combinations

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

vowels = {'a', 'e', 'i', 'o', 'u'}

for combi in list(combinations(basic, L)): # com = ('a', 't', 'c', 'i')
    for i in range(len(combi)-1):
        if basic[2] < combi[0]: # 첫 글자 종류 제한
            break
        if basic[i] > basic[i+1]: # 정렬 준수
            break
    result = ''.join(combi)  
    # 1 <= 모음의 수 <= (전체글자수-2:자음 2개) 일 때 조건을 만족
    if 1 <= sum(1 for r in result if r in vowels) <= (L-2):
        print(result)



# 0.1
from itertools import combinations

L, C = map(int, input().split())
basic = sorted(input().rstrip().split())
vowels = {'a', 'e', 'i', 'o', 'u'}

for combi in list(combinations(basic, L)): # com = ('a', 't', 'c', 'i')
    result = ''.join(combi)  
    if 1 <= sum(1 for r in result if r in vowels) <= (L-2):
        print(result)


# 1
from itertools import combinations

L,C = map(int,input().split())
arr = input().split()
arr.sort()
vowel = ['a', 'e', 'i', 'o', 'u']

for c in combinations(arr,L):
    vowel_cnt = sum(1 for ch in c if ch in vowel) # combinatino의 모음 갯수
    consonant_cnt = L - vowel_cnt # combinatino의 자음 갯수
    if vowel_cnt >= 1 and consonant_cnt >=2: # 일정 수 이상일 때 join
        print(''.join(c))
        

# 2: 백트래킹 (depth로 반복 return으로 범위 관리
# 모음 개수 구하는 함수
def check_password(password):
    count = 0
    for char in password:
        if char in {"a", "e", "i", "o", "u"}:
            count += 1
    return count
        
def make_password(depth, password): # password는 빈 문자열부터 시작
    if len(password) == L: # 길이 충족 시 
        count = check_password(password) # 자음모음 갯수 확인
        if count >= 1 and L - count >= 2: # 만족 시 출력
            print(password) 
        return # 글자수를 만족하면 return으로 끝내고 이전 재귀로 복귀
        
    # 0 ~ 입력 알파벳 갯수. s, t, w로 시작하는 경우까지 실행해 낭비 발생
    # 위에 if len(password) + (C - depth) < L: return으로 남은 알파벳 수가 적으면 바로 return
    for i in range(depth, C): 
        make_password(i + 1, password + alpabet[i])

L, C = map(int, input().split())
alpabet = sorted(list(input().split()))
make_password(0, "")

'''
>>> 문자열['a', 'c', 'i', 's', 't', 'w'] 길이에 따른 depth
→ make_password(0, "")
    ├─ i=0 → 'a' → make_password(1, "a")
    │   ├─ i=1 → 'c' → make_password(2, "ac")
    │   │   ├─ i=2 → 'i' → make_password(3, "aci")
    │   │   │   ├─ i=3 → 's' → make_password(4, "acis") ✔️조건검사
    │   │   │   ├─ i=4 → 't' → make_password(4, "acit") ✔️조건검사
    │   │   │   ├─ i=5 → 'w' → make_password(4, "aciw") ✔️조건검사
    │   │   ├─ i=3 → 's' → make_password(3, "acs")
    │   │   │   ├─ i=4 → 't' → make_password(4, "acst") ✔️조건검사
    │   │   │   ├─ i=5 → 'w' → make_password(4, "acsw") ✔️조건검사
    │   ├─ ...
    ├─ i=1 → 'c' → make_password(2, "c")
    ├─ ...
'''

고찰

유효한 해의 집합을 정의한다는 조건 때문에 combinations를 사용하는 쪽으로 접근했다. 순수하게 백트래킹만 사용하려 했다면 1) 조합을 순차적으로 구성해 나가는 처리 2) 모음 갯수를 세는 처리를 나누어 구성해야 했었을 것 같다.
combinations 대신 pertuation을 사용해서 헤맸다. "암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다"라는 문단 때문인데 combinations의 기본 연산을 생각하면 굳이 pertuation까지 꼬아생각할 필요가 없었다.
- combinations는 sorted된 인덱스 순차적 조합을 생성해주기 때문에 "증가하는 순서"로 배열되었다는 단서와 일치한다.
- permutations를 사용했을 때는 모든 순서를 고려하기 때문에 출제의도와 맞지 않음..!
#0.1을 보면 알겠지만, combinations를 사용하니 if문 두개가 불필요한 전제가 되었다
- 사전순 정렬된 인덱스에서 combination이 순차적으로 N개의 문자를 뽑을테니, 무엇으로 시작하는지 최소범위 제한이나 앞선 문자로 시작하는 인덱스만 활용해야 한다는 규칙이 불필요하다.
if 1 <= sum(1 for r in result if r in vowels) <= (L-2)를 구현하는 것이 익숙하지 않아 헤맸다.
- count를 써야하나 했었는데 for r in result 출력하려는 result의 원소 r이 vowel이라면 1을 return해서 result에 있는 전체 vowels 갯수를 구한다.
- 전체 vowels 갯수가 1개 이상이고, 전체 문자열 중 2개는 자음이어야 하니 L-2(최대 vowels 수)인 조건을 만족할 때 print한다.

chars.count(vowels) # ❌ 'vowels' 전체가 튜플에 포함되는지 보는 거라 의미 없음