https://www.acmicpc.net/problem/6443
문제 설명
- 주어진 단어의 철자를 재배열하여 만들 수 있는 모든 단어를 출력하는 프로그램을 작성합니다.
- 입력된 단어는 소문자로 이루어져 있으며, 알파벳 순서로 정렬된 상태로 출력해야 합니다.
- 동일한 애너그램은 한 번만 출력합니다.
예제 입력
2
abc
acba
예제 출력
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa
단계별 설명
1. 입력 처리
입력된 단어의 수와 각 단어를 읽어옵니다. 이를 위해 sys.stdin을 사용하여 표준 입력을 처리합니다.
_, *cases = stdin.readlines()
2. 애너그램 생성 함수
애너그램을 생성하는 핵심 함수인 find_anagrams를 구현합니다. 이 함수는 백트래킹 알고리즘을 사용하여 모든 가능한 조합을 생성합니다.
def find_anagrams(s):
res = []
s = sorted(s) # 단어를 알파벳 순서로 정렬합니다.
used = [False] * len(s) # 사용된 문자를 추적하기 위한 배열
backtrack(s, [], used, res)
return res
3. 백트래킹 함수
백트래킹 알고리즘을 사용하여 모든 가능한 애너그램을 생성합니다.
def backtrack(s, path, used, res):
if len(path) == len(s):
res.append("".join(path)) # 완성된 단어를 결과 리스트에 추가
return
for i in range(len(s)):
if used[i] or (i > 0 and s[i] == s[i - 1] and not used[i - 1]):
continue
used[i] = True
path.append(s[i])
backtrack(s, path, used, res)
path.pop()
used[i] = False
path: 현재까지의 조합을 저장하는 리스트used: 각 문자가 사용되었는지 추적하는 배열- 중복된 문자를 방지하기 위해 사용된 문자를 체크합니다.
4. 결과 출력
생성된 애너그램을 표준 출력으로 출력합니다.
for word in cases:
input_str = word.rstrip()
anagrams = find_anagrams(input_str)
stdout.write('\n'.join(anagrams) + '\n')
예제 실행 결과
위의 알고리즘을 사용하여 주어진 예제 입력을 처리한 결과는 다음과 같습니다:
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa
이 블로그 글에서는 애너그램을 생성하는 알고리즘을 백트래킹 기법을 통해 구현하고, 예제 데이터를 통해 알고리즘의 동작 원리를 설명했습니다. 각 단계에서 사용된 주요 개념과 코드의 역할을 이해함으로써, 애너그램 생성 문제를 효율적으로 해결할 수 있습니다.