엘리스는 이상한 나라의 국민이라면 누구나 즐겨 하는 하노이의 탑 놀이를 하고 있습니다. 하노이의 탑 놀이는 다음과 같이 진행됩니다.
게임은 1,2,3이 적혀있는 세 개의 막대와 N개의 지름이 다른 원판으로 시작합니다. N개의 원판은 지름이 큰 원판이 아래에 가도록 해서 1번 막대에 모두 꽂혀있습니다.
게임의 목표는 최소한의 횟수로 원판을 이동시키면서 N개의 원판을 모두 3번 막대로 옮기는 것입니다.
원판은 막대의 가장 위에 꽂혀있는 원판만 한 번에 하나씩 이동할 수 있습니다. ii번 막대의 가장 위에 꽂혀있는 원판을 jj번 막대의 가장 위로 옮기려면 j번 막대에 원판이 없거나 jj번 막대의 가장 위의 원판이 현재 원판보다 지름이 커야합니다.
하노이의 탑 놀이를 너무 많이 한 엘리스는 손이 아파서 원판을 옮기기 힘들어졌습니다. 엘리스를 대신해 막대의 원판을 옮겨주세요!
[입력]
첫째 줄에 원판의 개수 N이 주어집니다. (1≤N≤10)
[출력]
최소한의 횟수로 원판을 모두 1번 막대에서 3번 막대로 옮길 때, 원판의 이동 과정을 한 줄에 하나씩 출력합니다.
i번 막대의 원판을 j번 막대로 옮겼다면 i j를 출력합니다.
(출력할 때는, 각 줄마다 맨 뒤에 공백을 포함해서는 안된다.)
[예제 입력 1]
3
[예제 출력 1]
1 3
1 2
3 2
1 3
2 1
2 3
1 3
나의 답안
def hanoi(n):
hanoiSol(n,1,3)
def hanoiSol(n,start,end):
if n==1:
print(start,end)
else:
leftPoint=6-start-end
hanoiSol(n-1,start,leftPoint)
print(start,end)
hanoiSol(n-1,leftPoint,end)문제에서는 n만 주어지기때문에, 함수를 2개로 구성했다.
출발지는 1, 목적지는 3으로 고정이기때문에 남은 경유지는 6-(출발지+경유지)가 된다.
하노이의 탑 문제는 n이 1이 될때까지 함수를 반복하여 모든 블록을 다 옮기는 재귀함수를 활용한다.
예제 답안
