[프로그래머스] 하노이의 탑 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/12946#

프로그래머스

 

풀이 방법

 

하노이 방법은 인터넷에 좋은 글들이 많기에 간단히 설명하자면...

 

N-1개의 블럭을 FROM 에서 TMP로 옮기고 (tmp를 이용해)

N-1개의 블럭을 옮기고 맨 아래 남은 1개의 블럭을 FROM 에서 TO로 옮기고

TMP에 있는 N-1개의 블럭을 TO로 옮긴다(from을 이용해)

 

N이 1이라면 FROM에서 목적지 TO로 바로 옮겨준다.

전체 코드

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

void hanoi(int n, int from, int tmp, int to, vector<vector<int>> &answer) {
    
    vector<int> v;
    if(n==1) {
        // from -> to로 옮김
        v.push_back(from);
        v.push_back(to);
        answer.push_back(v);
    } else {
        
        // N-1개를 from -> tmp로 옮김
        hanoi(n-1, from, to, tmp, answer);
        
        // from에 있는 1개를
        // from -> to로 옮김
        v.push_back(from);
        v.push_back(to);
        answer.push_back(v);
        
        //tmp의 N-1개를 to로 옮김
        hanoi(n-1, tmp, from, to, answer);
    }
    return;    
}

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