[백준] 6443 애너그램 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/6443
• 🔑 DFS, 백트래킹
  
  • 딕셔너리에 알파벳 개수를 저장한다
    • ex) {a : 2, b : 1, c: 1}
  • 알파벳이 있으면(값이 0이 아니면)문자열에 추가, 딕셔너리에서 값을 내리고 다음 재귀로 간다.
    • 1. a
    • 2. aa
    • 3. aab
    • 4. aabc
    • 알파벳 다 썼으니까 출력하고 리턴 후 사용했던 알파벳 개수 다시 증가 (다른 순서로 다시 사용해봐야 함)
    • 2. aa
    • 3. aac
    • 4. aacb
    • 반복 ....

 

n = int(input())

def dfs(dict_s, l, s):
    if l == len(s):
        print(s)
        return

    for i in dict_s:
        if dict_s[i]:
            dict_s[i] -= 1
            dfs(dict_s, l, s+i)
            dict_s[i] += 1

for i in range(n):
    s = sorted(list(input()))

    dict_s = {}

    for i in s:             
        if i in dict_s:
            dict_s[i] += 1
        else:
            dict_s[i] = 1
    
    dfs(dict_s, len(s), "")