하노이의 탑

falcon940105·2021년 9월 12일
0

문제

풀이

1) n개의 원판에 대해 move메소드를 사용하여 1번 기둥에서 3번 기둥으로 옮긴다.

2) move메소드는 n-1개의 원판을 from 기둥에서 to 기둥을 이용하여 middle 기둥으로 옮긴다.

3) n 이 1일 때 from에서 to로 옮기고 그 값을 배열에 담아 list에 넣는다.

4) 2번 과정이 끝나면 원판을 from 에서 to 로 옮기고 그 값을 배열에 담아 list에 넣는다.

5) 마지막으로 n-1개의 기둥을 middle에서 from을 사용하여 to로 옮긴다.


C++

#include <string>
#include <vector>

using namespace std;

void hanoi_step(int n, char a, char b, char c, bool start, vector<vector<int>>& answer) {
    if (start) answer.clear();
  if (n) {
    hanoi_step(n-1, a, c, b, false, answer);
    answer.push_back({a, c});
    hanoi_step(n-1, b, a, c, false, answer);
  }
}

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


Java

import java.util.*;

class Solution {
    List<int[]> list;
 
    public void move(int from, int middle, int to, int n) {
        if (n == 1) {
            int[] arr = { from, to };
            list.add(arr);
        } else {
            move(from, to, middle, n - 1);
            int[] arr = { from, to };
            list.add(arr);
            move(middle, from, to, n - 1);
        }
 
    }

    
    public int[][] solution(int n) {
        int[][] answer;
        list = new ArrayList();
        move(1, 2, 3, n);
 
        answer = new int[list.size()][2];
 
        int i = 0;
        for (int[] a : list) {
            answer[i++] = a;
        }
 
        return answer;
    }
}


Python

def hanoi(num, start, to, mid, answer):
    if num == 1:
        return answer.append([start, to])
    hanoi(num-1, start, mid, to, answer)
    answer.append([start, to])
    hanoi(num-1, mid, to, start, answer)

def solution(n):
    answer = []
    hanoi(n, 1, 3, 2, answer)
    return answer

profile
공학을 잘하고 싶은 초짜

0개의 댓글