[프로그래머스] 하노이의 탑

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

하노이의 탑은 전형적인 재귀 문제이다. 하노이의 탑에 대한 원리는 해당 영상을 보면 쉽게 이해할 수 있다. 하노이의 탑에 대한 원리만 파악한다면 쉽게 해결할 수 있는 문제이다.

코드

C++

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

vector<vector<int>> ans;

void hanoi(int n, int from, int to, int by) {
    if (n == 1) {
        ans.push_back({ from, to });
        return;
    }
    hanoi(n - 1, from, by, to);
    ans.push_back({ from, to });
    hanoi(n - 1, by, to, from);
}

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

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<int[]> moves = new ArrayList<>();

    public void move(int from, int to) {
        moves.add(new int[]{from, to});
    }

    public void hanoi(int n, int from, int to, int by) {
        if (n == 1) {
            moves.add(new int[]{from, to});
            return;
        }
        hanoi(n - 1, from, by, to);
        moves.add(new int[]{from, to});
        hanoi(n - 1, by, to, from);
    }

    public int[][] solution(int n) {
        hanoi(n, 1, 3, 2);
        int[][] answer = new int[moves.size()][2];
        for (int i = 0; i < answer.length; i++)
            answer[i] = new int[]{moves.get(i)[0], moves.get(i)[1]};
        return answer;
    }
}