최장 경로 하노이탑

사이트 링크 : https://codeup.kr/problem.php?id=2698

 

문제는 아래와 같습니다.

문제

하노이 탑 게임에 대한 규칙은 잘 알고 있을 것이다. 

위 그림은 3개의 원판을 가지는 하노이 탑을 나타낸다. 이 게임의 목적은 A탑에 있는 1~3번까지의 원반을 C탑으로 모두 옮기는 것이다.
단, 다음 규칙을 지키면서 옮겨야 한다. 그리고 하노이2에서는 새로운 규칙 4)가 추가되었다.

1) 한 번에 하나의 원판만 옮길 수 있다.
2) 반드시 큰 원판 위에 작은 원판이 올라가야 한다.
3) 각 탑의 맨 위에 있는 원판만 옮길 수 있다.
4) 반드시 인접한 기둥으로만 원판을 옮길 수 있다.

만약 원판이 1개 라면, 

- 1번 원판을 A에서 B로 옮긴다.
- 1번 원판을 B에서 C로 옮긴다.


따라서 총 2번을 옮기면 모두 옮길 수 있다.

여러분은 n개의 원판이 주어질 때 이 원판을 옮기는 횟수 및 과정을 출력하는 프로그램을 작성하시오.

입력

• 첫 줄에 한 정수 n이 입력된다. (단, 1 <= n <= 12 )

출력

• 첫 번째 줄부터 한 줄에 하나씩 이동 경로를 "n : X->Y"행태로 출력한다. 
  마지막 줄에 총 옮긴 횟수를 출력한다.경로의 의미는 n번원판을 X기둥에서 Y기둥으로 옮긴다는 의미이다.

문제 해결 포인트 

• 하노이탑이라고 해서 재귀를 사용해야할줄 알았는데 문제 요구사항을 자세히 보면 DP 테이블을 만들푸는 문제입니다.
• 하노이탑을 하나씩 분석해보면 a[i] 가 전에 있던 a[i-1] 의 값을 앞으로 가는 방향 뒤로가는 방향이 중복이 됩니다.
• 문제를 푸는 점화식은 a[i] = a[i-1] + a[i]:A->B+ reverse(a[i-1]) + a[i]:B-> C + a[i-1] 입니다.

 

정답코드

 

복붙 가능코드

n = int(input())
dp = [[],[]]
dp[1] = [(1,'A','B'),(1,'B','C')]

def moveHanoi(n,X,Y):
    return str(n)+' : '+X+'->'+Y
    

for i in range(2,n+1):
    dp[i%2].clear()
    for j in dp[(i-1)%2]:
        dp[i%2].append(((j[0],j[1],j[2])))
    dp[i%2].append(((i,'A','B')))
    for j in reversed(dp[(i-1)%2]):
        dp[i%2].append((j[0],j[2],j[1]))
    dp[i%2].append(((i,'B','C')))
    for j in dp[(i-1)%2]:
        dp[i%2].append(j)

for i in dp[n%2]:
    print(moveHanoi(i[0],i[1],i[2]))
print(len(dp[n%2]))


dfs(a)
print(dp[a])

 

해당 문제는 계속 리뷰를 해서 코드를 정교화 해보는것도 좋은것 같습니다.