[C++로 풀이] 하노이의 탑 (재귀호출)⭐⭐⭐

📌 하노이의 탑

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

스스로 풀어낸 풀이가 아니다. 좀 고민해보다가 옛날에 자료구조 전공 수업에서 하노이 타워 코드를 다뤘던적이 있었던걸 기억하고 전공 책 꺼내 부랴부랴 이해해본 후 작성하는 풀이이다. 어려워!! ㅠㅠ

#include <string>
#include <vector>

using namespace std;

void HanoiTower(vector<vector<int>>& answer, int n, int start, int dest) {
    if (n == 1) {
        answer.push_back({ start, dest });
        return;
    }
    
    HanoiTower(answer, n - 1, start, 6 - start - dest);
    answer.push_back({ start, dest });
    HanoiTower(answer, n - 1, 6 - start - dest, dest);
}

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;
    HanoiTower(answer, n, 1, 3);
    return answer;
}

• 조건
  • 1️⃣ 한 번에 하나의 원판만 옮길 수 있음
    • 그러니 무조건 가장 위에 있는 원판부터 옮길 수 밖에 없음
  • 2️⃣ 큰 원판이 작은 원판 위에 있어서는 절대 안됨
    • 하나씩 이동 시키는 과정에서도 더 큰 원판이 늘 밑에 깔리도록 유지해야함

재귀적으로 생각해볼 것

    // "출발지 기둥" 👉 start (1,2,3 중 하나)
    // "도착지 기둥" 👉 dest (1,2,3 중 하나)
    // "나머지 기둥" 👉 6 - start - dest (기둥의 번호는 1,2,3 이므로)
    void HanoiTower(vector<vector<int>>& answer, int n, int start, int dest)

start 기둥에서 dest 기둥으로 n 개의 원판 옮기기.

• “출발지 기둥”, “나머지 기둥”, “목적지 기둥” 이렇게 3개의 기둥이 있고 "출발지 기둥" 👉 "목적지 기둥"으로 n개의 원판을 옮기려 한다면 !
  1. “출발지 기둥”에서 n - 1 개의 원판을 “나머지 기둥”으로 옮긴다.

       // 다음 단계의 출발지 : start
       // 다음 단계의 목적지 : 6 - start - dest (나머지 기둥)
       HanoiTower(answer, n - 1, start, 6 - start - dest);
     

  2. 그러면 “출발지 기둥”에 n개 중 가장 밑에 깔려있던 가장 큰 1개의 원판이 남아있을 텐데 얘가 “도착지 기둥”에서 맨 밑에 깔리게끔 “도착지 기둥”으로 옮겨 준다.

       answer.push_back({ start, dest }); // start 기둥에 남아있던 1 개를 dest 기둥에 옮겨줬다는 기록을 출력
     

  3. 1번에서 옮겼었던 “나머지 기둥”에 있는 n - 1개를 “목적지 기둥”으로 옮긴다.

       // 다음 단계의 출발지 : 6 - start - dest (나머지 기둥)
       // 다음 단계의 목적지 : dest
       HanoiTower(answer, n - 1, 6 - start - dest, dest);
     

1,3 과정에서 n-1개를 옮기는 과정또한 위 1,2,3 과정을 해주어야 하기 때문에 재귀적이다.

n = 4 일 때 1 번 기둥에서 3 번 기둥으로 옮기려 한다면

가장 큰 것부터 작은 것 까지 a,b,c,d 라는 이름을 붙여보았다. 종료 조건에서의 출력은 ⏰, 2️⃣ 번 과정에서의 출력은 2️⃣ 이모지를 붙임.

• HanoiTower(4, 1, 3) : 1 번 기둥에서 3 번 기둥으로 4 개를 옮기기
  • HanoiTower(3, 1, 2) : 1 번 기둥에서 2 번 기둥으로 3 개를 옮기기
    • HanoiTower(2, 1, 3) : 1 번 기둥에서 3 번 기둥으로 2 개를 옮기기
      • ⏰ HanoiTower(1, 1, 2) : 1 번 기둥에서 가장 위에 있는 d 1개를 2 번 기둥으로 옮기기
      • 2️⃣ 1 번 기둥에서 가장 위에 있는 c 1개를 3 번 기둥으로 옮기기

      • ⏰ HanoiTower(1, 2, 3) : 2 번 기둥에서 가장 위에 있는 d 1개를 3 번 기둥으로 옮기기

        

    • 2️⃣ 1 번 기둥에서 가장 위에 있는 b 1개를 2 번 기둥으로 옮기기

      

    • HanoiTower(2, 3, 2) : 3 번 기둥에서 2 번 기둥으로 2 개를 옮기기
      • ⏰ HanoiTower(1, 3, 1) : 3 번 기둥에서 가장 위에 있는 d 1개를 1 번 기둥으로 옮기기
      • 2️⃣ 3 번 기둥에서 가장 위에 있는 c 1개를 2 번 기둥으로 옮기기

      • ⏰ HanoiTower(1, 1, 2) : 1 번 기둥에서 가장 위에 있는 d 1개를 2 번 기둥으로 옮기기

        

  • 2️⃣ 1 번 기둥에서 가장 위에 있는 a 1개를 3 번 기둥으로 옮기기

    

  • HanoiTower(3, 2, 3) : 2 번 기둥에서 3 번 기둥으로 3 개를 옮기기
    • HanoiTower(2, 2, 1) : 2 번 기둥에서 1 번 기둥으로 2 개를 옮기기
      • ⏰ HanoiTower(1, 2, 3) : 2 번 기둥에서 가장 위에 있는 d 1개를 3 번 기둥으로 옮기기
      • 2️⃣ 2 번 기둥에서 가장 위에 있는 c 1개를 1 번 기둥으로 옮기기

      • ⏰ HanoiTower(1, 3, 1) : 3 번 기둥에서 가장 위에 있는 d 1개를 1 번 기둥으로 옮기기

        

    • 2️⃣ 2 번 기둥에서 가장 위에 있는 b 1개를 3 번 기둥으로 옮기기

      

    • HanoiTower(2, 1, 3) : 1 번 기둥에서 3 번 기둥으로 2 개를 옮기기
      • ⏰ HanoiTower(1, 1, 2) : 1 번 기둥에서 가장 위에 있는 d 1개를 2 번 기둥으로 옮기기
      • 2️⃣ 1 번 기둥에서 가장 위에 있는 c 1개를 3 번 기둥으로 옮기기

      • ⏰ HanoiTower(1, 2, 3) : 2 번 기둥에서 가장 위에 있는 d 1개를 3 번 기둥으로 옮기기

        

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기