[백준 | 실버1] 6443: 애너그램(백트랙킹, 순열, set, 중복저장방지)

https://www.acmicpc.net/problem/6443

 

문제

6443번: 애너그램

씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다.

애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다.

입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다.  또한 출력할 때에 알파벳 순서로 출력해야 한다.

입력

첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주어진다.

출력

N개의 영단어에 대한 모든 가능한 애너그램을 출력한다. 각각의 영단어에 대한 애너그램을 출력할 때, 알파벳 순서로 중복되지 않게 출력한다.

예제 입력 1 복사

2
abc
acba

예제 출력 1 복사

abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

 

중복저장 방지가 필요하다.

입력받은 단어가 한개가 아니므로 전역으로 처리하기 애매해다.

백트랙킹 하기 전에 중복된 단어를 돌지않아야한다,

 

실제 방문하고 넣고 백트랙킹 돌고 빼고 하기 전에 미리 선두로 temp에 값을 넣어보고

이 값이 사용된 값인지 아닌지 체크해야한다.

값을 리스트로 넣고 빼고 하고있으므로, copy()를 해주고, 바로 다음에 넣을 값은 + s[i]로 리스트 + 리스트 합치기 해준다.

set에는 list가 들어가지 않아서 tuple로 감싸서 넣어줘야한다...

import sys
sys.stdin = open("20220825_백준_6443_애너그램.txt", "r")

n = int(input())
sList = []

for _ in range(n) :
    sList.append(input())

#n개의 리스트에서 n개를 순열을 만들어라
def BACK(L, s, visited, result, recode) :
    #만들어진 문자열의 길이가 s와 같은 경우, 출력
    if L == len(s) :
        print("".join(result))
        return
    else :
        for i in range(len(s)) :
            if visited[i] is False :
                
                temp = result.copy()                #중복 출력 방지를 위해서 만들었던 result 복사
                temp.append(s[i])                   #이 다음에 들어갈 단어 일단 임시로 reult에 추가
                
                if tuple(temp) not in recode :      #set에 temp가 들어가 있지 않은 경우 BACK 실행
                    visited[i] = True
                    result.append(s[i])
                    recode.add(tuple(temp))         #만들 수 있는 단어니, set에 저장 -> tuple로 감싸야 리스트가 들어가진다.
                    BACK(L+1, s, visited, result, recode)
                    visited[i] = False
                    result.pop()

def solution(n, sList) :
    for s in sList :
        s = list(s)
        s.sort()                                    #알바펫 순서대로 출력해야해서 정렬 필요
        visited = [False] * len(s)
        result = []
        recode = set()
        BACK(0, s, visited, result, recode)

solution(n, sList)

# 2
# abc
# acba

#abc로 만들수 있는 3개 뽑는 순열 set로 저장하기
#acba로 만들 수 있는 4개 뽑는 순열 set로 저장하기