[재귀호출] 하노이탑

규칙

---

"만약 A,B,C 중에서 A에서 C로 원반이 이동해야 한다면, 가장 큰 원반을 제외한 나머지 원반들을 우선 B로 이동해야함"

 

어떠한 경우라도, 가장 큰 원반을 제외한 나머지 원반들은 목적지와 출발지를 제외한 나머지 축에 쌓아야 한다.

그리고 마지막 원반을 목적지에 가져다 놓은 후, 나머지 원반들을 다시 목적지로 이동시켜야 한다.

목적지로 이동할 때 또한, 위의 공식이 이뤄져야 한다.

 

 

"만약 출발 축을 1, 목적지 축을 3이라고 한다면 나머지 축 2를 구하는 공식은 (1+2+3) - (3+1) 이다. "

 

즉, 모든 원반에서 출발 축과 목적지 축을 빼면 나머지 축이 나온다는 의미이다.

 

풀이

---

재귀 함수로 해당 문제를 푼다면, 세 가지 흐름을 이용하여 문제를 해결하면 된다.

(1) 총 원반의 수가 n이라 했을 때 가장 큰 원반을 제외한 나머지 n-1개의 원반을 출발,목적지 축을 제외한 나머지 축에 모두 쌓아야 한다.

(2) 가장 큰 원반을 목적지 축으로 이동시킨다.

(3) 나머지 축에 쌓여져 있는 n-1개의 원반들을 목적지 축으로 모두 이동시킨다. 

 

"1,3번 과정에서 당연히 세 가지 흐름을 꼭 지켜야 한다. 따라서 재귀 호출로 해결하면 된다." 

 

코드

---

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
 
public class hanoiTower {
    public static void hanoi(BufferedWriter bw,int a, int b,int count) throws IOException {
        if(count == 1) {
            bw.write(a + " " + b + "\n");
            return;
        }    
        
        int goal = 6 - (a+b);
        hanoi(bw,a,goal,count-1); 
        bw.write(a + " " + b+ "\n");
        hanoi(bw,goal,b,count-1);    
        return;
    }
    
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write((1<<count)-1+ "\n");
        hanoi(bw,1,3,count);
        bw.close();
    }
}