💜 백준 11729번 하노이 탑 이동순서

1. 문제 설명

11729번 하노이 탑 이동 순서 링크

이동 순서를 Log로 찍어야 한다.

2. 푸는 원리

재귀를 이용한다.
(0) 재귀함수에는 출발지, 경유지, 도착지, 도착지까지 옮겨야 하는 원판의 번호가 있다.
(원판의 번호가 큰 것이 크기가 큰 것이다. 따라서 제일 작은 원판은 번호가 1이다.)

(1) 실제로 원판을 옮기는 것이 아니라, 그 이동 순서에 대한 로그만 찍는다.

 

[기저조건]
(1)옮겨야하는 원판의 번호가 0이 되면 그냥 return 한다.

 

[계산]
(1) 현재 옮겨야할 원판보다 작은 모든 원판을 경유지로 옮기는 Log를 찍는다. (재귀 이용)
(2) start와 end를 StringBuilder에 담아서 현재 원판의 이동을 Log로 찍는다. (StringBuilder에 담는 행위 자체가 옮기는 행위)
(3) 경유지에 있는 모든 원판을 현재 원판 위로 옮기는 Log를 찍는다. (재귀 이용)

 

[영상 풀이]

다음은 계산의 (1)의 재귀 과정을 영상으로 찍어보았다.
(3)은 덩어리째 이동으로 생략 했음으로, (1)번 부분이 어떻게 움직이는지 보고 이해해보자!

 

3. 코드 분석

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/*
* 11729번 [하노이 탑 이동 순서]
* */


public class Main {

    static StringBuilder sb = new StringBuilder();
    static int movingCnt = 0;

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

        // 1. 값 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 원판 갯수
        int diskCnt = Integer.parseInt(br.readLine());

        Hanoi(1,2,3, diskCnt);

        System.out.println(movingCnt);
        System.out.println(sb);
    }

    /*
    * Hanoi(출발지, 경유지, 도착지, 옮기는 원판의 넘버링)
    *  -> 먼저 diskNum-1 부터 그 위 원판들 모두를 경유지로 옮긴다. -> 이들은 경유지 자체가 최종 도착지가 됨.
    *  -> 맨 밑의 diskNum을 도착지로 옮긴다.
    *  -> diskNum-1 부터 그 윗부분 모두를 도착지로 옮긴다.
    * */
    public static void Hanoi (int start, int middle, int end, int diskNum) {

        if(diskNum == 0){
            return;
        }

        Hanoi(start, end, middle, diskNum-1);
        sb.append(start).append(" ").append(end).append("\n");
        movingCnt++;
        Hanoi(middle,start,end,diskNum-1);


    }
}