[JAVA] 백준 11729번 - 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

 

 

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

public class Main{
    static int cnt=0;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        move(n, 1,3,2);
        System.out.println(cnt);
        System.out.println(sb.toString());
    }

    public static void move(int n, int start, int end, int sub){
        if(n==1){
            cnt++;
            sb.append(start+" "+end+"\n");
            return;
        }

        move(n-1, start, sub, end);
        move(1, start, end, sub);
        move(n-1, sub, end, start);
    }
}

 

 

 

3개의 원판을 출발지, 목적지, 경유지로 정하자. 

 

과정을 3단계로 나눌 수 있다.

 

 

1. 맨 밑의 N번째 원판을 목적지로 옮기기 위해 n-1개의 원판을 경유지로 옮긴다.

2. n번째 원판 하나를 목적지로 옮긴다.

3. 경유지에 있는 n-1개의 원판을 목적지로 옮긴다. 

 

 

이 과정을 함수로 나타내면 이렇다.

 

처음 : start에서 sub를 거쳐 end로 총 n개의 원판을 운반

move(n, start, end, sub) 

 

1. start에 있는 n-1개의 원판을 모두 sub에 옮긴다. start가 출발지, sub가 목적지가 된다. 

move(n-1, start, sub, end)

 

2. 비어있는 end기둥에 1번에 남은 가장 큰 원판을 옮긴다.

move(1, start, end, sub)

 

3. 2번 기둥으로 옮긴 n-1 개의 원판을 3번 기둥으로 옮긴다. 

move(n-1, sub, end, start)

 

 

 

구글링해서 개념을 참고해 풀었다. 

카운트는 하노이탑 공식을 이용해 2의n승 -1 로도 출력할 수 있지만, 재귀 함수 호출시 카운트를 직접 더해 구해보았다.

 

 

 

 

참고 블로그 https://mgyo.tistory.com/185