91 삐약 : 백준 11729| 하노이탑 이동순서 [바킹독| 재귀 |JAVA]

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

 

 

package BKD_0x0B_Recursion;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class BOJ_11729 {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        bw.write(Integer.toString((1<<n)-1)+"\n");
        hanoi(1,3,n);

        bw.flush();
        bw.close();

    }

    static void hanoi(int a, int b, int n) throws IOException{
        if(n==1) {
            bw.write(a + " " + b + '\n');
            return;
        }

        hanoi(a,6-a-b,n-1);
        bw.write(a + " " + b + '\n');
        hanoi(6-a-b,b,n-1);
    }
}

 

 

 

---

 

 

풀이

 

 

focusing : N번 원판

N번 원판을 옮기기 위해서 N-1 까지의 모든 원판을 움직여야 함.

원판이 1개면 내가 원하는 곳으로 옮길 수 있다.
원판이 N개일 때 옮길 수 있으면, N+1개일 때도 옮길 수 있다. 

 

 

구현

 

#1. 함수 정의 

Q. 어떤 역할을 수행하는가?

원판 N개를 기둥 1에서 기둥 3으로 옮기는 방법을 출력하는 역할.

 

반례)

원판 N개를 기둥1에서 기둥 3으로 옮기려면 원판 N-1개를 기둥 3이 아닌 기둥 2로 옮겨야 함.

재귀의 성질인 f(N-1)성립 불가. => 적절하지 않은 정의

=> 재귀 사용 불가

 

 

 

 

#1. 함수 정의

void func(int a, int b, int n)

원판 N개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수

a : 시작지점 / b: 끝지점

 

 

#2. Base Condition

n==1 일 때 a에서 b로 원판 이동

 

#3. Recursion

a도 b도 아닌 기둥의 번호 == 6-a-b

1. n-1개의 원판을 a에서 6-a-b로 옮긴다.
2. n번 원판을 a에서 b로 옮긴다.
3. n-1개의 원판을 6-a-b에서 b로 옮긴다.