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

문제설명

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

제한사항

• n은 15이하의 자연수 입니다.
  
  

해결 방법

재귀를 설명할 때 피보나치 다음으로 자주나오는 하노이탑이다.

 

재귀를 사용했다.

 

n번째원판을 옮기기 위해서는 중간에 있는 기둥을 이용해 옮겨야한다.

 

n-1, n-2에도 공통적으로 적용되며, 1번째 원판만 바로 옮길 수 있다.

 

이 부분을 재귀로 구현한다.

 

옛날에 자료구조[저자 윤성우]책을 보고 엄청 공부했던게 생각나는데,

 

진짜 설명이 잘되어있었던 것 같다.

 

JAVA

package programmers;

import java.util.*;	

public class s_12946 {
	static ArrayList<int[]> ans = new ArrayList<>();
	public static void recur(int from, int by, int to, int n) {
		if(n == 1) {
			int[] a = {from, to};
			ans.add(a);
			return;
		}
		recur(from, to, by, n - 1);
		int[] a = {from, to};
		ans.add(a);
		recur(by, from, to, n - 1);
	}
	public static int[][] solution(int n){
		recur(1, 2, 3, n);
		int[][] r = new int[ans.size()][2];
		for(int i = 0; i < ans.size(); i++) {
			r[i][0] = ans.get(i)[0];
			r[i][1] = ans.get(i)[1];
		}
		return r;
	}
	
	public static void main(String[] args) {
		int[][] r = solution(2);
		
		for(int[] i : r) {
			System.out.println(i[0] + " " + i[1]);
		}
	}
}