[백준 알고리즘] 11729번 하노이탑 (Java)

 

하노이탑은 대표적인 분할정복 문제이다. n개의 원반을 이동시키는 문제는 n-1개의 원반을 이동시키는 문제로 세분화시킬 수 있고, 이를 반복하다보면 1개의 원반을 옮기는 것과 같다는 이론이다.

원반이 1개일 경우 그림으로 나타내면 다음과 같다.

즉 system.out.println(a+" "+c); 이다

원반이 2개일 경우

이때는 n-1개의 원반을 b로 옮기고(1단계), a에 있는 1개의 원반을 c로 옮긴 후(2단계), 나머지 n-1을 c로 옮긴다.

n이 어떤 수가 되든 이 과정을 반복하면 이동하는 횟수와 과정을 구할 수 있다.

 

참고)처음엔 하노이 탑의 옮긴 총 횟수가 2^n이기 때문에 pow함수를 써서 출력했는데 바로 시간초과가 뜨는 바람에 StringBuilder를 이용해 함수가 불릴때마다 출력 할 문자열을 붙이고 나중에 총 횟수를 insert함수를 이용해 stringbuilder 맨 앞 쪽에 붙여주었다. (String으로 연산하는 것보다 stringbuilder가 메모리 면에서 더 우수하다고 한다!)

 

 

 

코드

import java.util.*;
 
public class Main{
    public static int cnt=0;
    public static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        hanoi(n,1,2,3);
        sb.insert(0,cnt + "\n");
        System.out.println(sb);
    }
    public static void hanoi(int num, int a, int b, int c) {
        if(num==1){
            sb.append(a+" " +c+"\n");
            cnt++;
        }
        else {
            hanoi(num-1,a,c,b);//n-1개의 원반을 A에서 B로 이동
            sb.append(a + " "+c+"\n");
            cnt++;
            hanoi(num-1,b,a,c);//n-1개의 원반을 B에서 C로
        }
    }
}

문제 링크:

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