[백준] 1342 - 행운의 문자열

문제

백준 1342번 행운의 문자열

문제 링크 : https://www.acmicpc.net/problem/1342

 

 

문제 풀이

목적 : 주어진 문자열을 재배치하여, 인접한 모든 문자가 서로 다른 '행운의 문자열'을 만들 수 있는 모든 경우의 수를 구하는 것

이 문제의 목적에 따라, 모든 경우의 수를 탐색해야 하기 때문에 가능한 모든 문자열을 만들고 그것이 행운의 문자열인지 확인하는 방법을 사용했다. 이때 더 효율적인 탐색을 위해, 백트래킹 알고리즘을 사용했다. 가장 최근 붙인 문자가, 남은 다른 모든 문자와 같다면 행운의 문자열을 만들 수 없기 때문에 추가적인 탐색은 불필요하다. 이런 경우를 감지하여 최대한 적은 수의 탐색을 함으로써 브루트포스 방식보다 빠른 시간 안에 문제를 해결할 수 있다.

 

현재 만들고 있는 문자열(word)의 끝 문자에 대해, 남아있는(visited 배열에서 False 값을 갖는, 아직 사용하지 않은 문자) 모든 문자와 같다면 해당 문자열을 더 만들지 않고 그 전 문자로 되돌아간다. 만약 남아있는 문자 중 다른 문자가 있다면 word에 해당 문자를 붙여 bact 함수를 다시 호출한다. bact함수의 매개변수로 현재 word의 길이 l을 넣어, 만약 l이 n과 같다면 answer 이라는 set 자료구조에 추가한다. set 자료구조를 사용함으로써 중복 여부를 별도로 확인하지 않고 서로 다른 문자열의 수를 확인할 수 있다.

 

 

코드 

lst=list(map(str,input().rstrip()))

n=len(lst)

answer=set()
def bact(word,l):
  if l==n:
      answer.add(word)
      return
  for i in range(n):
    if not visited[i] and word[l-1]!=lst[i]:
      visited[i]=True
      bact(word+lst[i],l+1)
      visited[i]=False

for i in range(n):
  visited=[False]*n
  visited[i]=True
  bact(str(lst[i]),1)

print(len(answer))