[G5] 백준 11729번 하노이 탑 이동 순서 C++ 재귀

리뷰

 

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

기본적인 재귀 문제인 하노이 탑의 이동 순서 문제, 경로를 체크해야 하므로 직접 재귀를 돌려야 한다.

 

 

전역 변수

• n : 옮겨야 할 원판의 개수를 저장할 변수
• path : 원판을 옮기는 순서를 저장하기 위한 pair<int, int>타입의 벡터

 

함수

1. hanoi

void hanoi(int n, int from, int to, int aux)

 

재귀를 통해 1번 장대에서 3번 장대로 원판을 모두 옮기기 위한 함수

1. 매개변수로 옮길 원판의 개수 n, 시작 지점 from, 도착 지점 to, 임시 장대 aux를 매개변수로 받는다.
2. 기저 조건으로 원판이 한개만 남은 경우 path에 from, to를 추가해 주고 리턴해 준다.
3. n - 1개의 원판을 to를 임시 장대로 사용해 from에서 aux로 이동해 준다.
4. 재귀를 빠져나오며 path에 from, to를 추가해 준다.
5. 다시 재귀를 진행하며 n - 1개의 원판을 from을 임시 장대로 사용해 aux에서 to로 이동해 준다.

 

문제풀이

1. n값을 입력 받고 hanoi함수에 초기값 n, 1, 3, 2를 매개변수로 전달하여 호출한다.
2. 재귀 탐색을 마친 후 path의 size를 먼저 출력해 준 뒤 줄바꿈을 진행해 준다.
3. path에 저장된 이동 정보를 한줄에 한 개씩 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 하노이 탑 이동 순서 문제의 정답은 항상 2^n - 1의 값을 가진다.

 

정답 코드

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<pair<int, int>> path;

void hanoi(int n, int from, int to, int aux) {
    if (n == 1) {
        path.push_back({ from, to });
        return;
    }

    hanoi(n - 1, from, aux, to);
    path.push_back({ from, to });
    hanoi(n - 1, aux, to, from);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    hanoi(n, 1, 3, 2);
    cout << path.size() << "\n";
    for (const auto& i : path) cout << i.first << " " << i.second << "\n";

    return 0;
}