[재귀] 백준_11729_하노이탑_재귀_실버2

2021년 10월 03일 일요일 14시

 

백준_11729_하노이탑_재귀_실버2

 

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

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

public class Main {
	
	public static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		sb.append((int) Math.pow(2,N)- 1).append('\n');
		
		Hanoi(N,1,2,3);
		System.out.println(sb);
	
	}
	
	/*
	N : 원판의 개수 
	start : 출발지 
	mid : 옮기기 위해 이동해야 장소 
	to : 목적지
	 */
	
	public static void Hanoi(int N, int start, int mid, int to) {
		// 이동할 원반의 수가 1개라면?

		if(N ==1) {
			sb.append(start + " " +to + "\n" );
			return;
		}
		
		// STEP 1 : N-1개를 A에서 B로 이동 
		Hanoi(N-1, start, to, mid);
		
		// STEP 2 : 1개를 A에서 C로 이동 
		sb.append(start + " " + to + "\n");
		
		// STEP 3: N-1개를 B에서 로 이동 
		Hanoi(N-1, mid, start, to);
		
		
	}
}

 

 

<참고>

https://st-lab.tistory.com/96

[백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바]