[재귀] 하노이탑 이동순서 이해하기

 

 

A에 있는 탑을 C에 똑같이 쌓으려고 한다. 무조건 가장 큰 애를 밑에서 부터 쌓으려면 어떻게 해야할까?

재귀의 핵심은 큰 틀만 파악해서 코드를 짜고, 나머지 서브 경우의 수들은 틀만 잘 짜놓으면 알아서 딸려오게 끔 만드는 것이다. 

 

그러면 서브 경우의 수를 다 빼고, 가장 밑에 있는 파란색 블럭이 C에 오려면 어떻게 해야할까? 

 

우선 나머지 3개 블럭이 B에 있어야 한다. 그러면 파란색 블럭이 C로 이동할 수 있다.

 

이제 두번째로 큰 노란색 블럭이 C에 와야한다. 그러면 나머지 2개 블럭이 A에 있어야 노란색 블럭이 C로 갈 것이다.

 

 

 

연두색 블럭또한 마찬가지이다.

나머지 한개의 블럭을 B에 놓고 A에 C로 이동하면 된다.

 

즉 이 문제에서 중요한것은 가장 큰 블럭을 C로 옮기기 위해 나머지 블럭을 어딘가에 놓아야 한다는 것이다.(경유지)

 

정리하자면

1. n-1까지의 원반을 'A'에서 'B'로 이동한다. (원반 2개가 이동하는 것이므로 'C'를 한번 경유하게 된다)

2. 가장 밑에 있는 큰 원반을 'A'에서 'C'로 이동한다. 

3.작은 원반 n-1개를 'B'에서 'C'로 이동한다. (원반 2개가 이동하는 것이므로 'A'를 경유해야함)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
 
    public static int n;
    public static int cnt=0;
    public static StringBuilder sb=new StringBuilder();
 
    public static void hanoi(int num,int start,int via,int end){
 
        if(num==1){
            cnt++;
            sb.append(start).append(" ").append(end).append("\n");
            return;
        }else{
            cnt++;
 
            hanoi(num-1,start,end,via); //1에서 3을 거쳐 2로감
            sb.append(start).append(" ").append(end).append("\n"); //1에서 3으로감
            hanoi(num-1,via,start,end);//2에서 1을 거쳐 3으로 감
        }
 
    }
 
 
 
 
    public static void main(String[]args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());
        hanoi(n,1,2,3); //1에서 2를 거쳐 3으로 감
        System.out.println(cnt);
        System.out.println(sb.toString());
 
 
 
 
    }
 
 
 
}

 

제일 중요한건  n-1번째까지 애들을 2번으로 옮기고 n번째는 3번으로 옮겨야 한다.

그러기 위해서는 n-1번째까지 애들을 1번에서 3번을 거쳐 2번으로 

n번째를 1번에서 3번으로 (출력)

n-2번째 까지 애들을 2번에서 1번을 거쳐 3번으로 가야한다. 

 

https://brenden.tistory.com/31

[백준 11729] 하노이 탑 이동 순서