백준-11729번/하노이 탑 이동 순서(java)

 

 

문제 이해

 

하노이 탑의 이동 횟수를 수학 공식으로 나타내면 다음과 같다.

 

만약 원판이 2개일때의 이동 과정

원판 1 을 1---->2로 이동

원판 2 를 1---->3으로 이동

원판 1 을 2---->3으로 이동

 

만약 원판이 N개일때 이동 과정

원판 N-1 을 1---->2로 이동

원판 N 를 1---->3으로 이동

원판 N-1 을 2---->3으로 이동

 

 

문제 해결

 

 

매개변수 h1은 출발지, h3는 목적지로 표현

public static void move(int n,int h1,int h2, int h3) {
        if(n==1){
        sb.append(h1+" "+h3+"\n");
        return;
    }
    move(n-1,h1,h3,h2); //A --> B
    sb.append(h1+" "+h3+"\n"); // A --> C
    move(n-1,h2,h1,h3); // B --> C
}

이러면

만약 원판이 N개일때 이동 과정

원판 N-1 을 1---->2로 이동

원판 N 를 1---->3으로 이동

원판 N-1 을 2---->3으로 이동

위 과정을 구현 가능하다.

 

<전체 코드>

import java.util.Scanner;
import java.util.Stack;

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


        sb.append((int)Math.pow(2,N)-1).append('\n');
        move(N,1,2,3);
        System.out.println(sb);
    }

    public static void move(int n,int h1,int h2, int h3) {
            if(n==1){
            sb.append(h1+" "+h3+"\n");
            return;
        }
        move(n-1,h1,h3,h2); //A --> B
        sb.append(h1+" "+h3+"\n"); // A --> C
        move(n-1,h2,h1,h3); // B --> C
    }

}

 

고찰

아직 재귀함수에 익숙하지 않아서 많이 어려웠다.

재귀함수 문제를 많이 풀어야겠다.