JAVA_하노이 탑 이동 순서_재귀함수 알고리즘

자바 알고리즘-  구하는 알고리즘

시간 제한	메모리 제한
1 초	256 MB

 

▶ 나의 문제풀이 

[주요 메서드 및 설명]

 

1. 출력의 경우는 StringBuilder 사용

public static StringBuilder sb = new StringBuilder();

 

2. 제곱함수(2,N)-1

sb.append((int) (Math.pow(2, N) - 1)).append('\n');

 

자바에서 제곱을 계산하는 함수 Math.pow() 입니다.

함수: Math.power(double, double)

첫번째인자는 밑수이고, 두번째 인자는 지수입니다.

Math.pow(3,3) 이라고 하면 3의 3제곱이 계산을 하게 됩니다.

=3*3*3 =27

 

3. Hanoi(int N, int start, int mid, int to)

* N : 원판의 개수 / start : 출발지 1 / mid : 옮기기 위해 이동해야 장소 2 / to : 목적지 3

 

재귀는 기본적으로 함수 안에서 또다시 자기 자신(함수)을 호출하는 것이므로

하노이 함수 형태를 잘 보시면 N개의 원반수에서 -1 씩 감소하면서 반복적으로 재귀를 호출하고 있습니다.
그러다가 N==1 이 되면 출발지에서 목적지를 출력하고 빠져나오게 됩니다.

즉, 재귀함수를 쓰면서 가장 작은 원판 단위(N==1) 일 때까지 반복하면서 문제가 해결되게 됩니다.

 

Hanoi함수에서 두 번째 파라미터(start)와 네 번째 파라미터(to)를 이용하여 활용하는 원리인데

정말 풀면서 해답 보면서 너무 어려워서... 힘들었던 문제입니다...

 

아래 유용한 여러 해설을 남겨놓겠습니다.

 

 

▶ 나의 코드 

package algorithm.doit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 하노이탑이동순서 {
	//출력의 경우는 StringBuilder 사용
	public static StringBuilder sb = new StringBuilder();

	//메인에서 재귀함수를 불러 사용할 예정
	public static void main(String[] args) throws IOException {
		 
		// N : 원판의 개수 , start : 출발지 1 , mid : 옮기기 위해 이동해야 장소 2 ,to : 목적지 3

		System.out.println("원판의 개수를 입력하시오");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


		// 원판의 개수를 N에 저장
		int N = Integer.parseInt(br.readLine());
		//				제곱함수(2,N)-1 을 해줍니다
		sb.append((int) (Math.pow(2, N) - 1)).append('\n');

		Hanoi(N, 1, 2, 3);
		System.out.println(sb);

	}

	public static void Hanoi(int N, int start, int mid, int to) {
		// 이동할 원반의 수가 1개라면?
		if (N == 1) {
			sb.append(start + " " + to + "\n");
			return;
		}

		// A -> C로 옮긴다고 가정할 떄,
		// STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 mid 지점으로 옮긴다.)
		Hanoi(N - 1, start, to, mid);

		// STEP 2 : 1개를 A에서 C로 이동 (= start 지점의 N번째 원판을 to지점으로 옮긴다.)
		sb.append(start + " " + to + "\n");

		// STEP 3 : N-1개를 B에서 C로 이동 (= mid 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
		Hanoi(N - 1, mid, start, to);

	}
}

 

 

 

 

 

<참고>

코딩 테스트: https://www.acmicpc.net/

Baekjoon Online Judge

https://study-all-night.tistory.com/6

[백준 11729번] 하노이 탑 이동순서 - Python(파이썬) 자세한 풀이

https://hyunipad.tistory.com/89

[백준 알고리즘][자바] 11729번 : 하노이 탑 이동 순서