백준-하노이 탑 이동 순서(11729번)

유명한 하노이탑 문제입니다.

 

입력으로 원판의 갯수 n 을 입력받으면 

최소 이동 횟수를 출력해주고 그 과정을 출력할것을 요구하고 있습니다.

 

---

하노이탑의 패턴

 

모든 재귀함수가 그렇듯이 패턴을 찾는것이 중요합니다.

 

하노이탑의 패턴은 크게보면

1. 가장 아랫부분 원판을 제외한 나머지를 잠깐 1->2번으로 옮겨놓는다.
2. 가장 아랫부분 원판을 1->3으로 옮긴다
3. 2에 옮겨놓았던 원판들을 2->3으로 옮겨놓는다.

이 패턴을 인지하는 순간 재귀함수를 세우는건 쉬워집니다.

---

하노이탑 최소 이동 횟수

하노이탑의 최소 이동횟수는 (2의 n승)-1 입니다.

 

그 이유는 

위에서 말한 규칙을 보면 알 수 있습니다.

 

• 가장 아랫부분 원판을 제외한 나머지를 잠깐 1->2번으로 옮겨놓는다.
• 가장 아랫부분 원판을 1->3으로 옮긴다
• 2에 옮겨놓았던 원판들을 2->3으로 옮겨놓는다.

n일때의 이동횟수는 n-1일때의 이동횟수 *2+1이 됩니다.

 

이를 이용하면

 

n==1일때의 이동횟수는 1입니다.

n==2일때는 3

n==3일때는 7

n==4일때는 15 

...

 

이를 일반화하면 (2의 n승)-1이 나오게됩니다.

이는 비트이동연산자를 활용해서 표현하면

(1<<n)-1

 

---

코드

Hanoi함수 매개변수:

• from:출발칸
• to:도착칸
• temp:중간에 거쳐가는 칸
• n:원판갯수

#include<iostream>
using namespace std;

void Hanoi(int from, int to, int temp, int n)
{
    if(n==1)
    {
        cout<<from<<" "<<to<<"\n";
    }
    else
    {
        Hanoi(from,temp,to,n-1);
        cout<<from<<" "<<to<<"\n";
        Hanoi(temp,to,from,n-1);
    }
}

int main()
{
    int input;
    cin>>input;

    cout<<(1<<input)-1<<"\n"; //최소 이동 횟수
    Hanoi(1,3,2,input);
}

Hanoi함수 부분의 else부분을 보면 위에서 말했던 규칙을 그대로 적용해놓은걸 알 수 있습니다.

 

 

 

• 가장 아랫부분 원판을 제외한 나머지를 잠깐 1->2번으로 옮겨놓는다.

Hanoi(from,temp,to,n-1);

 

• 가장 아랫부분 원판을 1->3으로 옮긴다

cout<<from<<" "<<to<<"\n";

 

• 2에 옮겨놓았던 원판들을 2->3으로 옮겨놓는다.

Hanoi(temp,to,from,n-1);