[백준] 12906. 새로운 하노이 탑

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

문제요약

• 막대가 세개 있음 : A, B, C
• 원반은 세 종류가 있음 : A, B, C
• 원반 개수의 합은 10
• 원반 크기는 같음. 이동은 가장 위에 있는 것에서 이동
• 원반의 종류에 해당하는 막대로 가는데 최소 이동 횟수

접근법

• 경우의 수를 구해보자
  • 원반 10개가 쭉 나열되었다고 치면 10! = 3,628,800
  • 3 그룹으로 나눠야하는데, 나열된 것들에서 사이 공간 2개를 고르는 경우의 수로 볼 수 있으니까 ${_9C_2 = 36}$
  • A, B, C 중복 나열을 나눠줘야하는데, 나누는 수가 가장 적게 하려면 균등하게 해서 3!, 3!, 4! = 864
  • ${10! \times _9C_2 \div 3! \div 3! \div 4!= 151,200}$
• 한번 이동할 때 6가지 경우의 수
• 151,200 상태를 갖는 가지가 6개인 그래프의 BFS
• 상태 저장 방법
  • ("ABC", "CC", "AAAB") 같은 vector를 유지해가면서 map 이용