[Python] 백준 1342: 행운의 문자열

 백트래킹은 예전에도 나를 많이 괴롭힌 문제다. 모든 케이스를 다 보는 것이라서, 시간초과, 메모리초과가 항상 뒤따라다니는 알고리즘이기 때문이다. 그렇기에 적절하게 제약조건을 걸어줘서 시간복잡도와 메모리 관리를 모두 잡아내야한다.

문제

민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다.

예제 입력 1

aabbbaa

예제 출력 1 

1

예제 입력 2 

ab

예제 출력 2 

2

 

예제 입력 4 

abcdefghij

예제 출력 4

3628800

 

정답 코드

result = 0
S = input()

resultStrings = set()

def isLuckyString(s) -> bool:

    if len(s) <= 1:
        return True
    
    if s[0] == s[1]:
        return False
    if s[-1] == s[-2]:
        return False

    for i in range(1, len(s)-1):
        if s[i-1] == s[i] or s[i] == s[i+1]:
            return False

    return True

def dfs(s, index):

    global result, S, visited

    if index in visited:
        return 
    
    if not isLuckyString(s):
        return 
    
    if len(s) == len(S) and isLuckyString(s) and s not in resultStrings:
        result += 1
        resultStrings.add(s)
        return 
    
    visited.append(index)

    for n in range(len(S)):
        dfs(s + S[n], n)       

    visited.remove(index) 


for start in range(len(S)):
    visited = []
    dfs(S[start], start)

print(result)

 

 행운의 문자열 판별 함수를 분리해놓고, DFS를 시행한다. 다만 중간에 길이가 완성되지 않더라도 행운 문자열이 아니면 DFS를 중간에 멈춰야하는데, 그 부분을 놓쳐서 실패를 좀 하다가 뒤늦게 깨달았다.