- Problem Link : https://www.acmicpc.net/problem/1759
문제
- C개의 문자들 중에 L개의 문제를 골라서 암호를 만든다.
- 암호는 최소 한개의 모음, 최소 두 개의 자음으로 구성되어야 한다.
- 암호는 알파벳이 암호에서 증가하는 순서로 배열되어있다.
입력
- 첫째 줄, 두 정수 L, C
- 둘째 줄, C개의 문자들
출력
- 각 줄에 하나씩, 사전식으로 가능성 있는 암호 모두를 출력
풀이
"중복 없이", "n개를 선택한다"라는 규칙을 통해 조합(combination)이 떠올랐다. C개의 문자들 중에서 L개의 문제를 골라서 암호를 만드는 경우의 수는 이라고 할 수 있다. 코드로는 itertools 모듈의 combinations 함수를 사용해서 모든 조합을 구할 수 있다.
- 이 때 출력의 결과가 사전식으로 정렬되어있으므로 애초에 조합을 생성하기 전에 문자들이 들어있는 리스트를 정렬한 후에 조합을 생성해준다.
combi = list(itertools.combinations(alpha, L))- 위와 같은 코드를 이용하면 combi 안에 튜플의 형태로 문자들이 담긴 리스트(alpha)에서 L개의 원소를 꺼내서 만들 수 있는 모든 조합이 저장된다.
조합을 꺼냈으면 해당 조합, 즉 암호가 우리가 원하는 조건에 만족하는지 확인해서 만족할 경우 출력한다.
- 모음 1개 이상, 자음 2개이상의 조건을 만족해야한다.
- 정렬된 리스트에서 조합을 생성했기에 만들어진 조합들도 모두 정렬된 상태이다.
if c in ["a", "e", "i", "o", "u"]:
consonant += 1
else:
vowel += 1이처럼 문자 c가 모음에 속할 경우 consonant를 +1 해주고 그 외의 경우에는 vowel을 +1 해준다. 한 조합에 대해서 위 과정이 끝나면 모음과 자음 개수를 비교해서 조건에 만족할 경우 출력해준다.
오류 및 해결
조합(combination)을 이용한 코드를 작성한 후 오류 없이 결과 또한 정상적으로 출력되었다. 추가적으로 해당 문제를 백트래킹(back-tracking) 알고리즘으로도 해결할 수 있다고 해서 백트래킹 알고리즘에 대해 알아보았다.
백트래킹(back-Tracking) 알고리즘
백트래킹이란?
해를 찾는 도중 해가 아니어서 막힐 경우, 되돌아가서 다시 해를 찾아가는 기법으로 최적화 문제와 결정 문제를 푸는 방법이 되기도 한다.
- 자세히 설명하자면 해를 찾는 과정에서 모든 경우의 수를 방문하는 것이 아니라 한정 조건에 한해서 모든 경우의 수를 시도하는 것이다. 실제로 다중 반복문이나 DFS 방식처럼 모든 경우의 수를 확인하는 경우보다 백트래킹 알고리즘을 통해 한정 조건에서의 모든 경우의 수를 시도하는 것으로 한정 조건을 만족하지 않는 상당한 경우의 수들을 배제시켜 더 빠르게 실행이 가능하다.
백트래킹의 구현
백트래킹의 구현은 대부분 BFS나 DFS와 함께 구현한다. 모든 경우의 수에서 한정 조건을 만족하는 경우를 탐색하는 것으로 어떤 노드의 유망성, 즉 해가 될만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전으로 돌아가(Backtracking)하여 다음 분기, 자식 노드로 간다. 해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning)한다고 한다.
적용
따라서 이 문제에 백트래킹 알고리즘을 적용해서 풀려면 먼저 DFS 방식으로 모든 문자를 순차적으로 방문하는데 DFS 진행 깊이가 L이 된다면 더 이상의 진행을 멈추고 자음과 모음 개수를 판단하는 과정으로 바로 넘기면 된다.
코드
1. 조합론
import sys
import itertools
input = sys.stdin.readline
L, C = map(int, input().split())
alpha = input().split()
alpha.sort()
combi = list(itertools.combinations(alpha, L))
ans = []
for s in combi:
consonant = 0
vowel = 0
for c in s:
if c in ["a", "e", "i", "o", "u"]:
consonant += 1
else:
vowel += 1
if consonant >= 1 and vowel >= 2:
for c in s:
print(c, end="")
print()
2.백트래킹
import sys
import itertools
input = sys.stdin.readline
L, C = map(int, input().split())
alpha = sorted(list(map(str, input().split())))
answer = []
def back_tracking(deep, idx):
if deep == L:
consonant = 0
vowel = 0
for c in answer:
if c in ["a", "e", "i", "o", "u"]:
consonant += 1
else:
vowel += 1
if consonant >= 1 and vowel >= 2:
print("".join(answer))
return
for i in range(idx, C):
answer.append(alpha[i])
back_tracking(deep + 1, i + 1)
answer.pop()
back_tracking(0, 0)
