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

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

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

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

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

2. 입력

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

3. 예제

n	result
2	[ [1,2], [1,3], [2,3] ]

4. 풀이

하노이의 탑 퍼즐을 풀어나가는 방법을 먼저 알아야 문제를 쉽게 풀 수 있습니다.

 

하노이의 탑은 1번 막대에 있는 링을 모두 3번 막대로 최소 횟수로 이동하는 것이 목표입니다.

 

예를 들어 n이 3인 하노이의 탑은 1번 막대에 있는 링은 가장 큰 링을 제외 한 나머지 링들을 모두 2번 막대에 가져다 놓고 마지막을 1번 막대의 링을 3번 막대로 이동 시키는 것이 가장 처음 해야될 목표입니다.

 

그 다음은 2번 막대에 있는 n이 2인 하노이의 탑을 다시 가장 큰 링을 제외한 나머지 링들을 모두 1번 막대에 가져다 놓고 마짐가으로 2번 막대의 링을 3번 막대로 이동 시키는 것이 두번째 목표 입니다.

 

최종 적으로 1번 막대에 있는 가장 작은 링을 3번 막대로 이동하면 n이 3인 하노이의 탑 퍼즐을 풀 수 있습니다.

 

위 과정을 같은 과정들을 묶어 재귀를 도출 할 수 있습니다.

 

여기서 가장큰 빨간링을 1번 막대에서 3번 막대로 옮기기 위해서 노란링과 초록링을 2번으로 옮기는 작업이 필요하며 이 과정에서 3번 막대를 임시로 사용하는 과정이 있습니다.

 

1번 막대의 빨간링을 3번 막대로 이동 시키면 이제 2번 막대에 n-1개의 하노이의 탑이 생성 되었습니다.

 

이제 2번 막대에 n-1개의 하노이의 탑이 생성 되었기 때문에 다시 하노이의 탑 풀이과정을 반복 합니다.

 

단 이번에는 출발 막대가 1번이 아닌 2번이며 임시로 사용가능 한 막대가 2번이 아닌 1번 막대가 됩니다.

 

이렇게 재귀 호출을 통해 하노이의 탑 문제를 풀 수 있습니다.

 

5. 코드

전체 코드는 Git에 있습니다.

private int index = 0;
public int[][] solution(int n) {
	int[][] answer = new int[(int)Math.pow(2, n) - 1][2];

	hanoi(n,1, 3, 2, answer);

	return answer;
}

public void hanoi(int n, int start, int dest, int waypoint, int[][] answer){
	if(n == 1)
		answer[index++] = new int[] {start, dest};
	else{
		hanoi(n-1, start, waypoint, dest, answer);//가장 큰 링을 제외한 나머지를 2번 막대로 이동
		answer[index++] = new int[] {start, dest};//최종 가장 큰 링을 1번에서 3번으로 이동
		hanoi(n-1, waypoint, dest, start, answer);//n-1 하노이의 탑을 다시 반복하기 위해 재귀호출
	}
}