하노이 탑 이동 순서 풀이

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

백준 재귀 6단계 - 11729번 하노이 탑 이동 순서를 풀어보았다.

 

풀이: 하노이 탑을 재귀함수로 작성하면 된다.

 

C++

#include <iostream>
#include<cmath>

using namespace std;

void hanoi(int k,int a, int b, int c)
{
  if(k==1) printf("%d %d\n",a,b);
  else
  {
    hanoi(k-1,a,c,b);
    printf("%d %d\n",a,b);
    hanoi(k-1,c,b,a);
  }
}

int main()
{
  int n;
  scanf("%d",&n);
  cout << (int)pow(2,n)-1 << "\n";
  hanoi(n,1,3,2);
}

Python

import math

def hanoi(t,a,b,c):
	if t==1: print(a,b)
	else:
		hanoi(t-1,a,c,b)
		print(a,b)
		hanoi(t-1,c,b,a)

n=int(input())
print(int(math.pow(2,n))-1) # 옮긴 횟수
hanoi(n,1,3,2)

Java