[백준] 11729_하노이 탑 이동순서 / 재귀

 

 

Gold

 

 

문제

 

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다.

각 원판은 반경이 큰 순서대로 쌓여있다.

이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

 

 

입력

 

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

 

출력

 

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두

번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

 

 

---

 

 

풀이

 

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

class Main {
    static int count;
    static StringBuilder sb;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sb = new StringBuilder();
        count = 0;

        hanoi(N, 1, 3, 2);

        System.out.println(count);
        System.out.println(sb);
        
        sc.close();
        
    }

    public static void hanoi(int num, int from, int to, int other){
        if(num==0) return;
        hanoi(num-1, from, other, to);
        sb.append(from + " " + to + "\n");
        hanoi(num-1, other, to, from);
        count += 1;
    }
}

 

N개의 원반을 목표 기둥으로 옮기기 위해서는

1. N-1개의 원반을 다른 기둥 (other) 으로 모두 옮긴 후

2. 맨 마지막 기둥을 목표 기둥(to)으로 옮긴 후 

3. 다른 기둥에 있던 모든 원반을 목표 기둥으로 옮겨야 한다.

 

이때 다른 기둥에 있는 원반도 위와 같은 절차를 모두 거쳐야 한다.

결국 하노이의 탑은 같은 작업이 반복적으로 실행되어야 함을 알 수 있고, 이는 재귀함수를 사용하여 해결할 수 있다.

 

public static void hanoi(int num, int from, int to, int other){

    // 더이상 옮겨야 할 원반이 없을 경우 재귀호출을 종료한다. 
    if(num==0) return;
    
    // 1. n-1개의 원반을 other 기둥으로 옮긴다. 
    hanoi(num-1, from, other, to);

    // 2. 가장 큰 원반을 from에서 to 기둥으로 옮기는 작업을 기록한다. 
    sb.append(from + " " + to + "\n");
    
    // 3. n-1개의 원반을 other에서 to 기둥으로 옮긴다. 
    hanoi(num-1, other, to, from);
    
    // 원반이 이동할 때마다 count를 증가시킨다 
    count += 1;
}

• num :옮겨야하는 원반의 개수
• from : 원반이 현재 위치한 기둥
• to : 원반의 이동 목표 기둥
• other : 나머지 한 기둥

 

 

 

이미지출처 : craftofcoding

 

 

* 참고 - C++ 풀이

https://strong-2-min.tistory.com/491

[프로그래머스] 하노이의탑 / 재귀함수

 

 

---

 

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