하노이탑 이동 공식

 

하노이탑은 알고리즘 문제로 너무 유명하지만, 난 이번에 처음 풀어봤다.

단순 구현문제인 줄 알았는데, 재귀 문제로 유명한 것이었다.

 

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

11729번: 하노이 탑 이동 순서

 

 

 

---

1. 이동 갯수 공식

---

 

하노이탑은 이동할 때마다 신경써줘야 하는 것이 있다. 바로 쌓아 놓은 원판은 항상 위의 것이 아래 것보다 작아야 한다는 공식이다. 이걸 고려하여 이동 갯수를 1부터 세워주면 일정한 숫자로 증가하는 것을 확인할 수 있다.

 

원판 1개

(1,3) -> 1회 이동

 

 

원판 2개

(1,2)

(1,3)

(2,3) -> 3회 이동

 

 

원판 3개

(1,3)

(1,2)

(3,2)

(1,3)

(2,1)

(2,3)

(1,3) -> 7회 이동

 

 

원판 4개

(1,3)

(1,2)

(3,2)

(1,3)

(2,1)

(2,1)

(3,2)

(1,2)

(1,2)

(1,3)

(2,1)

(2,1)

(2,3)

(1,3)

(1,3) -> 15회 이동

 

 

1 -> 3 -> 7 -> 15 . . .  즉, 2의 n승 만큼 수가 늘어난다. 즉, 공비수열이다.

이 공비수열의 일반항은 an = 2^n-1이다.

 

 

 

---

 

2. 이동 방식

---

 

 

이동방식은 간단하다. 1번 2번 3번 장대가 있다고 가정한다.

 

1. 2번 장대에 가장 큰 원판을 제외한 N-1개의 원판을 여러 장대를 활용해 순서대로 정리한다.

2. 가장 큰 원판을 3번 장대에 이동한다.

3. 2번 장대에 쌓여있던 원판을 여러 장대를 활용해 3번 장대에 크기 순서대로 정리한다.

 

이를 재귀적으로 풀이해나가는 것이다.

 

import java.util.*;
import java.io.*;

class Main {

    static StringBuilder sb = new StringBuilder();

    public static void hanoi(int N, int start, int mid, int to){
        if(N==1){
            sb.append(start+" "+to).append("\n");
            return;
        }

        //step1 : start -> mid
        hanoi(N-1, start, to, mid);

        //step2 : start -> end (가장 큰 수)
        sb.append(start+" "+to).append("\n");

        //step3: mid -> to (나머지 원반 모두 옮기기)
        hanoi(N-1, mid, start, to);
    }
}

 

 

 

 

---

3. 전체 코드

---

 

import java.util.*;
import java.io.*;

class Main {

    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);
    }

    public static void hanoi(int N, int start, int mid, int to){
        if(N==1){
            sb.append(start+" "+to).append("\n");
            return;
        }

        //step1 : start -> mid
        hanoi(N-1, start, to, mid);

        //step2 : start -> end (가장 큰 수)
        sb.append(start+" "+to).append("\n");

        //step3: mid -> to (나머지 원반 모두 옮기기)
        hanoi(N-1, mid, start, to);
    }
}

 

StringBuilder를 사용해 화면 출력 횟수를 비약적으로 줄여준다.