[알고리즘/C++]하노이탑알고리즘

재귀함수를 이용하는 하노이탑 알고리즘에 대해 공부하였다.

 

하노이탑 알고리즘은 재귀적인 방법을 이용해 구현할 수 있다.

하노이탑 문제의 규칙

1. 세 개의 기둥이 있고, 첫 번째 기둥에는 크기가 다른 n개의 원판이 쌓여 있다.
2. 각 원판은 크기가 다르며, 작은 원판이 큰 원판 위에 쌓일 수 있다.
3. 한 번에 하나의 원판만 이동할 수 있으며, 큰 원판 위에 작은 원판이 있을 수 없다.
4. 기존의 기둥에서 목표의 기둥에 처음과 같은 형태로 쌓는 것이 목표다.

 

자세하게 파악이 가능한 예시 이미지 는 아래쪽에..

이미치 출처 : https://travelerfootprint.tistory.com/108

단순하게 이게 왜 재귀함수인가 몰랐으나..

동영상을 찾아보고 공부해본결과 어찌저찌 납득이 되긴 했다..

 

*주의할점*

• 함수는 스택영역에 순서대로 쌓인다.
• 재귀함수는 탈출 조건을 함수내부에서 재귀하는 함수보다 위에 있어야 탈출 할 수 있다.
• 탈출좋건이 없다면 함수가 스택영역이 넘칠때까지  쌓이기 때문에 스택오버플로우가 생길 수 있다.
• 이해를 위해서 꼭 중단점을 찍고 함수가 어떻게 호출되는지 순서대로 파악해야한다.

#include <iostream>

using namespace std;

void hanoi(int n, int from, int mid, int to) // 함수 (횟수, 첫기둥, 중간기둥, 마지막기둥)
{
    // 재귀 함수를 이용한 하노이탑
    if (n == 1) // 재귀함수는 탈출조건이없을경우 무한반복 스택오버플로우가 생긴다.
    {	
        cout << "원반 " << n << " 을 " << from << " 에서 " << to << " 으로이동" << endl;
        return; // 꼭 반환으로 탈출해주도록 한다.
    }
    // 가장아래를 제외한 위쪽들을 순서대로 경우지로 이동시키는것
    hanoi(n - 1, from, to, mid);
    
    // 가장아래의 원반은 바로 도착지로 이동시키는것 출력
    cout << "원반 " << n << " 을 " << from << " 에서 " << to << " 으로이동" << endl;
    
    // 경우지에 있는 것들을 시작점을 통해서 도착지로 이동시키는것
    hanoi(n - 1, mid, from, to);
}

int main()
{
    cout << "원반 갯수 : ";
    int num;
    cin >> num;
    hanoi(num, 1, 2, 3);

    return 0;
}

위의 코드로 3을 입력한 출력 결과

 

 

 

이해를 참고한 영상

https://www.youtube.com/watch?v=Xu5GC_7YIeQ 

 

 

하노이탑 관련 백준 문제

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

1914번: 하노이 탑

 

++ 챗 GPT 에서 확인한 하노이탑 알고리즘

#include <iostream>
using namespace std;

void hanoi(int n, char from, char to, char temp) {
  if (n == 1) {
    cout << from << " -> " << to << endl;
  } else {
    hanoi(n-1, from, temp, to);
    cout << from << " -> " << to << endl;
    hanoi(n-1, temp, to, from);
  }
}

int main() {
  int n;
  cout << "원반의 개수를 입력하세요: ";
  cin >> n;

  hanoi(n, 'A', 'C', 'B');

  return 0;
}

이 코드에서 hanoi() 함수가 하노이탑 알고리즘을 구현합니다.

 

함수는 n개의 원반을 from 기둥에서 to 기둥으로 옮기는 함수이며, temp 기둥을 보조로 사용합니다.

n이 1일 때는 단순히 from 기둥의 맨 위에 있는 원반을 to 기둥으로 옮기면 되므로 출력합니다.

그렇지 않을 경우에는 n-1개의 원반을 from 기둥에서 temp 기둥으로 옮긴 뒤, 맨 아래에 있는 원반을 to 기둥으로 옮긴 뒤, 다시 n-1개의 원반을 temp 기둥에서 to 기둥으로 옮기는 과정을 반복합니다.

 

main() 함수에서는 원반의 개수 n을 입력받고, hanoi() 함수를 호출합니다.

이때 첫 번째 기둥을 A로, 두 번째 기둥을 C로, 세 번째 기둥을 B로 지정합니다.

따라서 이 코드는 A 기둥에 있는 n개의 원반을 C 기둥으로 옮기는 과정을 출력합니다.